Cod sursa(job #3134515)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 29 mai 2023 11:20:08
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <bits/stdc++.h>

using namespace std;

struct segNode {
    long long sum;
    segNode(long long x = 0) : sum(x) {}
    friend segNode operator+(const segNode &s1, const segNode &s2) {
        return segNode(s1.sum + s2.sum);
    }
};

class segTree {
private:
    int segSize;
    vector<segNode> seg;
    void rangeUpdateUtil(int p, int l, int r, int lQ, int rQ, long long vQ) {
        int m = (l + r) / 2;
        if (lQ > r || rQ < l)
            return;

        if (lQ <= l && r <= rQ) {
            seg[p].sum += vQ;
            return;
        }

        rangeUpdateUtil(p + 1, l, m, lQ, rQ, vQ);
        rangeUpdateUtil(p + 2 * (m - l + 1), m + 1, r, lQ, rQ, vQ);

        seg[p] = seg[p + 1] + seg[p + 2 * (m - l + 1)];
    }
    int prefQueryUtil(int p, int l, int r, int pQ) {
        if(l == r)
            return l;
        int m = (l + r) / 2;

        if(pQ <= seg[p + 1].sum)
            return prefQueryUtil(p + 1, l, m, pQ);
        else
            return prefQueryUtil(p + 2 * (m - l + 1), m + 1, r, pQ - seg[p + 1].sum);
    }

public:
    segTree(int n) {
        seg.resize(2 * n);
        segSize = n;
    }
    void pointUpdate(int l, long long x) {
        rangeUpdateUtil(0, 0, segSize - 1, l, l, x);
    }
    segNode rangeQuery(int l) {
        return prefQueryUtil(0, 0, segSize - 1, l);
    }
};

const int nmax = 3e4;

int n;
int a[nmax + 2];
int ans[nmax + 2];

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    segTree arb(n + 1);
    for(int i = 1; i <= n; i++)
        arb.pointUpdate(i, 1);
    for(int i = n; i >= 1; i--){
        int x = arb.rangeQuery(a[i]).sum;
        arb.pointUpdate(x, -1);
        ans[x] = i;
    }
    for(int i = 1; i <= n; i++)
        cout << ans[i] << "\n";
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0), cerr.tie(0);
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);

    int q = 1;
    // cin >> q;
    while(q--){
        solve();
    }
    return 0;
}