Cod sursa(job #1902103)

Utilizator raulmuresanRaul Muresan raulmuresan Data 4 martie 2017 13:34:12
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
/*Folosim Arbori de intervale
*/
#include<fstream>
#include<vector>
#include<string>
const int NMAX =  30000;

using namespace std;

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

int i, n, k, j, m, nr, sol, x , y;
int MaxArb[4 * NMAX + 5], a[30005];
int result[30005];

void query(int nod, int stanga, int dreapta, int value)
{
    if(stanga == dreapta)
    {
        //fout <<stanga<<"\n";
        sol = stanga;
        MaxArb[nod] = 0;
        return;
    }
    int mij = (stanga + dreapta) / 2;
    if(value <= MaxArb[2 * nod])
    {
        //value = value - MaxArb[2 * nod];
        query(2 * nod, stanga, mij, value);
    }
    else
    {
        value = value - MaxArb[2 * nod];
        query(2 * nod + 1, mij + 1, dreapta, value);
    }
    MaxArb[nod] = MaxArb[2 * nod] + MaxArb[2 * nod + 1];
}


void update(int nod, int stanga, int dreapta, int position)
{
    if(stanga == dreapta)
    {
        MaxArb[nod] = 1;
        return;
    }
    int mij = (stanga + dreapta) / 2;
    if(position <= mij)
    {
        update(2 * nod, stanga, mij, position);
    }
    else
    {
        update(2 * nod + 1, mij + 1, dreapta, position);
    }
    MaxArb[nod] = MaxArb[2 * nod] + MaxArb[2 * nod + 1];
}

int main()
{
    fin >> n;
    for(i = 1; i <= n; i++)
    {
        fin >> a[i];
        update(1, 1, n, i);
    }
    for(i = n; i >= 1; i--)
    {
        sol = -1;
        query(1, 1, n, a[i]);
        //fout << sol<<"\n";
        result[sol] = i;
    }

    for(i = 1; i <= 2*n; i++)
    {
        //fout << MaxArb[i] << " ";
    }
    //fout <<"\n";

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