Cod sursa(job #2705807)

Utilizator mihnea.anghelMihnea Anghel mihnea.anghel Data 13 februarie 2021 12:47:50
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#define f in
#define g out

using namespace std;
ifstream in ( "schi.in" );
ofstream out( "schi.out" );
int n, i, x, ind;
int v[30300], aint[130000], poz[30300];

void build ( int nod, int st, int dr ){
    if ( st == dr )
        aint[nod] = 1;
    else {
        int mid = (st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
        aint[nod] = aint[2*nod]+aint[2*nod+1];
    }
}

int query ( int nod, int st, int dr, int loc ){
    if ( st == dr )
        return st;
    int mid = (st+dr)/2;
    if ( aint[2*nod] >= loc )
        return query(2*nod, st, mid, loc);
    return query(2*nod+1, mid+1, dr, loc-aint[2*nod]);
}

void update ( int nod, int st, int dr, int p ){
    if ( st == dr )
        aint[nod]--;
    else {
        int mid = (st+dr)/2;
        if ( p <= mid )
            update(2*nod, st, mid, p);
        else update(2*nod+1, mid+1, dr, p);
        aint[nod] = aint[2*nod]+aint[2*nod+1];
    }
}

int main() {
    f>>n;
    for ( i=1; i <= n; i++ )
        f>>v[i];
    build ( 1, 1, n );
    
    for ( i=n; i; i-- ){
        ind = query ( 1, 1, n, v[i] );
        update ( 1, 1, n, ind );
        poz[ind] = i;
    }
    
    for ( i=1; i <= n; i++ )
        g<<poz[i]<<"\n";
    return 0;
}