Cod sursa(job #3324987)

Utilizator McMeatGhenea Radu Stefan McMeat Data 24 noiembrie 2025 13:44:09
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fein("schi.in");
ofstream g("schi.out");
#define NMAX 30005
#define INF 100010
#define pii pair<int,int>

int a[NMAX], n;


struct segment_tree {
    vector<int> v;
    int p2;

    segment_tree(int n) {
        p2=1;
        while(p2<n) {
            p2<<=1;
        }
        v.assign(p2*2, 0);
    }
    void build(int nod, int l, int r) {
        if(l==r) {
            v[nod]=1;
        }
        else {
            int mid=(l+r)/2;
            build(nod*2, l, mid);
            build(nod*2+1, mid+1, r);
            v[nod]=v[nod*2]+v[nod*2+1];
        }
    }
    void update(int nod, int l, int r, int pos, int val) {
        if(l==r) {
            v[nod]=0;
        }
        else {
            int mid=(l+r)/2;
            if(pos<=mid) {
                update(nod*2, l, mid, pos, val);
            }
            else {
                update(nod*2+1, mid+1, r, pos, val);
            }
            v[nod]=v[nod*2]+v[nod*2+1];
        }
    }
    int get_pos(int nod, int l, int r, int pos) {
        if(l==r) {
            return l;
        }
        else {
            int mid=(l+r)/2;
            if(v[nod*2]>=pos) {
                return get_pos(nod*2, l, mid, pos);
            }
            else {
                return get_pos(nod*2+1, mid+1, r, pos-v[nod*2]);
            }
        }
    }
} aint=segment_tree(0);

vector<int> r;
void solve() {
    aint.build(1, 1, n);
    for(int i=n;i>0;i--) {
        int pos=aint.get_pos(1, 1, n, a[i]);
        r[pos]=i;
        aint.update(1, 1, n, pos, 0);
    }
    for(int i=1;i<=n;i++) {
        g<<r[i]<<'\n';
    }
}

void read_data() {
    fein>>n;
    aint=segment_tree(n);
    r.assign(n+1, 0);
    for(int i=1;i<=n;i++) {
        fein>>a[i];
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    read_data();
    solve();

    return 0;
}