Cod sursa(job #2953634)

Utilizator matei0000Neacsu Matei matei0000 Data 11 decembrie 2022 20:45:48
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>

using namespace std;

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

long long aint[120005];
int v[30005];
int v2[30005];

long long join(long long a, long long b)
{
    return a+b;
}

void update(long long st, long long dr, long long poz, long long k)
{
    if(st>k || dr<k)
        return;
    if(st==dr)
    {
        aint[poz]--;
        return;
    }
    long long mid=(st+dr)/2;
    update(st,mid,2*poz,k);
    update(mid+1,dr,2*poz+1,k);
    aint[poz]=join(aint[2*poz],aint[2*poz+1]);
    return;
}

long long query(long long st, long long dr, long long poz, long long nr)
{
    if(st==dr)
        return st;
    long long mid=(st+dr)/2;
    if(aint[2*poz]>=nr)
        return query(st,mid,2*poz,nr);
    else
        return query(mid+1,dr,2*poz+1,nr-aint[2*poz]);
}

void build(int st, int dr, int poz)
{
    aint[poz]=dr-st+1;
    if(dr-st>0)
    {
        int mid=(st+dr)/2;
        build(st,mid,2*poz);
        build(mid+1,dr,2*poz+1);
    }
}


int main()
{
    long long n;
    cin>>n;
    for(long long i=1;i<=n;i++)
        cin>>v[i];
    build(1,n,1);
    for(long long i=n;i>0;i--)
    {
        long long x=query(1,n,1,v[i]);
        update(1,n,1,x);
        v2[x]=i;
    }
    for(long long i=1;i<=n;i++)
        cout<<v2[i]<<'\n';
    return 0;
}