Cod sursa(job #2801045)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 14 noiembrie 2021 18:56:00
Problema Schi Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n, clas[30005], sol[30005], arbint[65005], first, last;

void precalc(int nod, int st, int dr)
{
    if(st == dr)
    {
        arbint[nod] = 1;
        return;
    }
    int med = (st + dr) / 2;
    precalc(2 * nod, st, med);
    precalc(2 * nod + 1, med + 1, dr);
    arbint[nod] = arbint[2 * nod] + arbint[2 * nod + 1];
}

void update(int nod, int st, int dr, int val, int ind)
{
    if(st == dr)
    {
        arbint[nod] = 0;
        sol[st] = ind;
        return;
    }
    int med = (st + dr) /2;
    if(val <= arbint[2 * nod])
        update(2 * nod, st, med, val, ind);
    else
        update(2 * nod + 1, med + 1, dr, val - arbint[2 * nod], ind);
    arbint[nod]--;
}


int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> clas[i];
    precalc(1, 1, n);
    for(int i = n; i >= 1; i--)
        update(1, 1, n, clas[i], i);
    for(int i = 1; i <= n; i++)
        fout << sol[i] << '\n';
    return 0;
}