Cod sursa(job #1680289)

Utilizator andreeainfo_dAndreea Dutulescu andreeainfo_d Data 8 aprilie 2016 17:10:46
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
int a[30005],aint[120005],v[30005],i,n,p;
void update(int nod, int st, int dr, int poz, int val)
{
    int mij;
    if(st==dr)
    {
        aint[nod]=val;
        return;
    }
    mij=(st+dr)/2;
    if(poz<=mij)update(nod*2, st, mij, poz,val);
    else update(nod*2+1, mij+1, dr, poz,val);
    aint[nod]=aint[nod*2]+aint[nod*2+1];
}
void query(int nod, int st, int dr, int x, int y, int loc)
{
    int mij;
    if(x<=st&&dr<=y)
    {
        if(st==dr)
        {
            if(p>st)p=st;
            return;
        }
    }
    mij=(st+dr)/2;
    if(x<=mij&&aint[nod*2]>=loc)query(nod*2, st, mij, x, y,loc);
    else if(y>mij) query(nod*2+1,mij+1,dr,x,y,loc-aint[nod*2]);
}
int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        update(1,1,n,i,1);
    }
    for(i=n;i>=1;i--)
    {
        p=n;
        query(1,1,n,v[i],n,v[i]);
        a[p]=i;
        update(1,1,n,p,0);
    }
    for(i=1;i<=n;i++)
        printf("%d\n",a[i]);
    return 0;
}