Cod sursa(job #2902105)

Utilizator octavi26octavian octavi26 Data 15 mai 2022 16:45:48
Problema Schi Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#define N 15008

using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

int n;
int v[N];
int T[4 * N];
int sol[N];

void update1( int left, int right, int nod, int poz, int x )
{
    if( left == right )
        T[nod] = x;
    else
    {
        int pivot = ( left + right ) / 2;
        if( poz <= pivot )
            update1( left, pivot, nod << 1, poz, x );
        else
            update1( pivot + 1, right, nod << 1|1, poz, x );

        T[nod] = T[nod << 1] + T[nod << 1|1];
    }
}

void update2( int left, int right, int nod, int x, int poz )
{
    if( left == right )
        T[nod] = 0, sol[left] = poz;
    else
    {
        int pivot = ( left + right ) / 2;
        if( x <= T[nod << 1] )
            update2( left, pivot, nod << 1, x, poz );
        else
            update2( pivot + 1, right, nod << 1|1, x - T[nod << 1], poz );

        T[nod] = T[nod << 1] + T[nod << 1|1];
    }
}

int query( int left, int right, int nod, int i, int j )
{
    if( i <= left && right <= j )
        return T[nod];

    int a = 0, b = 0;
    int pivot = ( left + right ) / 2;
    if( i <= pivot )
        a = query( left, pivot, nod << 1, i, j );
    if( j > pivot )
        b = query( pivot + 1, right, nod << 1|1, i, j );

    return a + b;
}

void Citire()
{
    int i;
    fin >> n;
    for( i=1; i<=n; i++ )
    {
        fin >> v[i];
        update1( 1, n, 1, i, 1 );
    }
}

void Rezolvare()
{
    int i;
    for( i=n; i>0; i-- )
    {
        update2( 1, n, 1, v[i], i );
    }

    for( i=1; i<=n; i++ )
        fout << sol[i] << "\n";
}

int main()
{
    Citire();
    Rezolvare();
    //cout << sizeof( Lee ) / 1024.0 / 1024.0;
    return 0;
}