Cod sursa(job #3240541)

Utilizator EricRaiaEricRaia EricRaia Data 16 august 2024 11:11:41
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>

using namespace std;

///ifstream cin ("schi.in");
///ofstream cout ("schi.out");

int n,clasament[300005],a[300005],aint[1200005];

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

void update(int nod, int st, int dr, int poz)
{
    if (st==dr)
        aint[nod]=0;
    else{
        int mij=(st+dr)/2;
        if(poz<=mij)
            update(nod*2, st, mij, poz);
        else
            update(nod*2+1, mij+1, dr, poz);
        aint[nod]=aint[nod*2]+aint[nod*2+1];
    }
}

int query(int nod, int st, int dr, int k)
{
    if(st==dr)
        return st;
    else{
        int mij=(st+dr)/2;
        if(aint[nod*2]>=k)
            return query(nod*2, st, mij, k);
        else
            return query(nod*2+1, mij+1,dr, k-aint[nod*2]);
    }
}

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1, 1, n);
    for (int i=n;i>=1;i--){
        int poz=query(1, 1, n, a[i]);
        clasament[poz]=i;
        update(1, 1, n, poz);
    }
    for(int i=1;i<=n;i++)
        cout<<clasament[i]<< '\n';

    return 0;
}