Cod sursa(job #3171120)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 18 noiembrie 2023 13:22:16
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 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]--;
    update(poz/2);
}
int build( int st, int dr, int nod ){
    if( st == dr )
        return 1;
    int mij = ( st + dr ) / 2;
    return seg_tree[nod] = build(st, mij, nod*2) + build(mij+1, dr, 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;
    }
    int top = 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;
}