ZBdWhb - Online C++ Compiler & Debugging Tool

#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define pb push_back
#define fin(a, n) for(int i = a; i < n; i++)
#define fjn(a, n) for(int j = a; j < n; j++)
#define all(a) a.begin(),a.end()
#define allr(a) a.rbegin(),a.rend()
#define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

using namespace std;

const double pi = acos(-1);
const int N = 1000+20;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;

string di[] = {"D","L", "U", "R", "UL", "UR", "DL", "DR"};
int dx[] = {+1, +0, +0, -1, -1, -1, +1, +1};
int dy[] = {+0, -1, +1, +0, -1, +1, -1, +1};
char dc[] = {'D', 'L', 'R', 'U'};

struct segTree {
    ll treeSize;
    vector<ll> used;
    ll n;
    segTree(ll n) {
        treeSize = 1;
        this->n = n;
        while (treeSize < n) treeSize <<= 1;
        used.resize(2 * treeSize, -oo);
    }

    void build() {
        for (ll i = 0; i < treeSize; i++) {
            if (i < n)
                used[treeSize - 1 + i] = 1;
            else
                used[treeSize - 1 + i] = 0;
        }

        for (ll i = treeSize - 2; i >= 0; i--)
            used[i] = used[2*i+1] + used[2*i+2];
    }

    void change(ll k, ll i, ll l, ll r) {
        if (r-l == 1) {
            used[i]  = 0;
            return;
        }

        ll mid = l+(r-l)/2;
        if (k < mid) change(k, 2*i+1, l, mid);
        else change(k, 2*i+2, mid, r);

        used[i] = used[2*i+1] + used[2*i+2];
    }

    void change(ll k) {
        change(k, 0, 0, treeSize);
    }

    ll query(ll k, ll i, ll l, ll r) {
        if (r-l == 1) {
            return l;
        }

        ll mid = l+(r-l)/2;
        if (used[2*i+2] >= k)
            return query(k, 2*i+2, mid, r);
        return query(k - used[2*i+2], 2*i+1, l, mid);
    }

    ll query(ll k) {
       ll x =  query(k, 0, 0, treeSize);
        change(x);
        return x;
    }
};

void solve() {
    ll n;  cin >> n;
    vector<ll> v(n);
    fin(0, n) cin >> v[i];
    segTree st(n);
    st.build();
    vector<ll> ans(n, 0);
    for (ll i = n-1; i >= 0; i--) {
        ll idx = st.query(v[i]+1);
        ans[i] = idx+1;
    }

    for (auto x : ans) cout << x << " ";
    cout << "\n";
}

int main() {
    FAST;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int tt = 1; //cin >> tt;
    while (tt--) {
        solve();
        //cout << "Case #" << c++ << ": ";
    }
    return 0;
}