Cod sursa(job #3334690)

Utilizator vlad_binVlad Bintintan vlad_bin Data 19 ianuarie 2026 10:32:18
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;

struct AIB
{
    AIB(int n) : n(n), n_log(__lg(n)), aib(vector<int>(n + 1)) {}
    void update_sum(int pos, int value)
    {
        if (pos > n) return;
        aib[pos] += value;
        update_sum(pos + (pos & -pos), value);
    }
    int query(int pos)
    {
        return query(pos, 0);
    }
    int binary_search(int value)
    {
        if (value < aib[1])
            return -1;
        int ans = 0;
        for (int p = n_log; p >= 0; p--)
        {
            if (ans + (1 << p) > n)
                continue;
            if (aib[ans + (1 << p)] < value)
            {
                ans += 1 << p;
                value -= aib[ans];
            }
        }
        return ans;
    }

    private:
    int query(int pos, int sum)
    {
        if (pos <= 0) return sum;
        return query(pos - (pos & -pos), sum + aib[pos]);
    }
    int n;
    int n_log;
    vector<int> aib;
};

int main()
{
    #ifdef INFOARENA
    ifstream cin("schi.in");
    ofstream cout("schi.out");
    #endif
    int n;
    cin >> n;
    vector<int> data(n);
    vector<int> ans(n);
    for (auto &x : data)
        cin >> x;
    reverse(data.begin(), data.end());
    AIB aib(n);
    for (int i = 1; i <= n; i++)
        aib.update_sum(i, 1);
    for (int i = 0; i < n; i++)
    {
        int idx = aib.binary_search(data[i]);
        ans[idx] = n - i;
        aib.update_sum(idx + 1, -1); 
    }
    for (auto x : ans)
        cout << x << '\n';
}