Cod sursa(job #3259781)

Utilizator AndreiDragosDavidDragos Andrei David AndreiDragosDavid Data 27 noiembrie 2024 19:57:25
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n, m;
const int MAXN = 100000;
int aint[4 * MAXN];

int query(int node, int start, int end, int k) {
    if(start==end) return start;

    int mid = (start+end)/2;

    if(aint[2*node]>=k)
        return query(2*node, start, mid, k);
    else
        return query(2*node+1, mid+1, end, k-aint[2*node]);
}

void update(int node, int start, int end, int idx){
    if(start==end)
        aint[node] = 0;
    else{
        int mid = (start+end)/2;

        if(idx<=mid)
            update(2*node, start, mid, idx);
        else
            update(2*node+1, mid+1, end, idx);

        aint[node] = aint[2*node] + aint[2*node+1];
    }
}

void build(int node, int start, int end) {
    if (start == end)
        aint[node] = 1;
    else{
        int mid = (start+end)/2;

        build(2*node, start, mid);
        build(2*node+1, mid+1, end);

        aint[node] = aint[2*node]+aint[2*node+1];
    }
}

int32_t main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
#endif
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    vector<int> a(n);

    for (int i = 0; i < n; ++i)
        cin >> a[i];

    build(1, 1, n);

    vector<int> ans(n,0);

    for(int i=n-1; i>=0; --i){
        int pos=query(1,1,n,a[i]);
        ans[pos-1]=i+1;
        update(1,1,n,pos);
    }

    for(int i=0; i<n; ++i)
        cout << ans[i] << '\n';

    return 0;
}