Cod sursa(job #3171130)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 18 noiembrie 2023 13:36:15
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
const int NMAX = 30001;
int seg_tree[4*NMAX];
int sol[NMAX+1];
int v[NMAX+1];
int baga( int st, int dr, int nod, int val ){
    if( st == dr )
        return st;
    int mij = ( st + dr ) / 2;
    if( val > seg_tree[nod*2] )
        return baga( mij+1, dr, nod*2+1, val - seg_tree[nod*2] );
    return baga( st, mij, nod*2, val );
}
/*void update( int poz ){
    if( poz == 0 )
        return;
    seg_tree[poz]--;
    cout << "in\n";
    update(poz/2);
    cout << "out\n";
}*/

void update(int poz) {
    while( poz ) {
        seg_tree[poz]--;
        poz /= 2;
    }
}

/*void update(int node_lf, int node_rg, int update_pos, int node = 1) {
    if (node_lf == node_rg) {
        seg_tree[node] = 0;
        return;
    }

    int med = (node_lf + node_rg) / 2;
    if (update_pos <= med) {
        update(node_lf, med, update_pos, 2 * node);
    } else {
        update(med + 1, node_rg, update_pos, 2 * node + 1);
    }
}*/

void build( int st, int dr, int nod ){
    if( st == dr )
        return;
    int mij = ( st + dr ) / 2;
    build(st, mij, nod*2);
    build(mij+1, dr, nod*2+1);
    seg_tree[nod] = seg_tree[nod*2] + seg_tree[nod*2+1];
}
int main()
{
    int n;
    in >> n;
    int log2n = log2(n);
    log2n += ((1 << log2n) < n);
    int size_ = 1 << log2n;
    for( int i = 1; i <= n; i++ ){
        in >> v[i];
        seg_tree[i+ size_ - 1] = 1;
    }
    build(1, n, 1);
    for( int i = n; i > 0; i-- ){
        int poz = baga(1, n, 1, v[i] ) + size_ -1;
        update(poz);
        sol[poz - size_ +1] = i;
    }
    for( int i = 1; i <= n; i++ )
        out << sol[i] << "\n";
    return 0;
}