Cod sursa(job #2986165)

Utilizator e_ggIonescu Dorian e_gg Data 27 februarie 2023 20:41:59
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");

const int nmax = 30005;

int a[3 * nmax], v[nmax], sol[nmax];
int n;

void constr( int nod, int st, int dr) {
    if ( st == dr )
        a[nod] = 1;
    else {
        int mij = ( st + dr ) / 2;
        constr( 2 * nod, st, mij );
        constr( 2 * nod + 1, mij + 1, dr );
        a[nod] = a[2 * nod] + a[2 * nod + 1];
    }
}

void update(int poz, int val, int nod, int st, int dr) {
    if ( st == dr ) {
        a[nod] = 0;
        sol[st] = val;
    }
    else {
        int mij = ( st + dr ) / 2;
        if ( a[2 * nod] >= poz )
            update( poz, val, 2 * nod, st, mij );
        else
            update( poz - a[2 * nod], val, 2 * nod + 1, mij + 1, dr );
        a[nod] = a[2 * nod] + a[2 * nod + 1];
    }
}

int main()
{
    f >> n;
    for ( int i = 1; i <= n; i++ )
        f >> v[i];
    constr(1, 1, n);
    for ( int i = n; i >= 1; i-- )
        update(v[i], i, 1, 1, n);
    for ( int i = 1; i <= n; i++ )
        g << sol[i] << '\n';
    f.close();
    g.close();
    return 0;
}