Cod sursa(job #3301202)

Utilizator ifrimdragosIfrim Dragos ifrimdragos Data 23 iunie 2025 10:26:14
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>

using namespace std;

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


const int nmax = 30005;

///we 'll use node to keep in mind the number of free cells in that interval

int nrfree[3 * nmax];
int sol[nmax];
void build(int node , int st , int dr)
{

    if(st == dr)
    {
        nrfree[node] = 1;
        return ;
    }
    int mid = (st + dr) >> 1;
    build(2 * node , st , mid);
    build(2 * node + 1 , mid + 1, dr);
    nrfree[node] = nrfree[2 * node] + nrfree[2 * node + 1];

}
int query(int node , int st , int dr , int poz)
{
    if(st == dr)
    {
        return st;
    }
    int mid = (st + dr) >> 1;
    if(nrfree[2 * node] >= poz)
        return query(2 * node , st , mid , poz);
    else
        return query(2 * node + 1 , mid + 1 , dr , poz - nrfree[2 * node]);
}


void update(int node , int st , int dr , int poz )
{
    if(st == dr)
    {
        nrfree[node] = 0;
        return;
    }
    int mid = (st + dr) >> 1;
    if(poz <= mid)
    {
        update(2 * node , st , mid , poz);
        nrfree[node] = nrfree[2 * node] + nrfree[2 * node + 1];

    }


    else
        {
        update(2 * node + 1, mid + 1 , dr, poz);
        nrfree[node] = nrfree[2 * node] + nrfree[2 * node + 1];

    }
}

int main()
{
    int n ;
    fin >> n;
    int p[n + 1];
    for(int i = 1;i <= n;i++)
    {
        fin >> p[i];
    }

    build(1 , 1 , n);

    for(int i = n ;i >= 1; i--)
    {
        int poz = query(1 , 1 , n , p[i]);
        sol[poz] = i;
        update(1 , 1 , n , poz);
    }

    for(int i = 1; i <= n; i++)
    {
        fout << sol[i] << '\n';
    }
    return 0;
}