Cod sursa(job #855825)

Utilizator marialivia16Chiorean Maria Livia marialivia16 Data 15 ianuarie 2013 18:00:16
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<cstdio>
#define MAXN 32768
int n,arb[MAXN*3],value,index,poz_i[MAXN],poz_f[MAXN];
void UpdateArb(int nod,int st,int dr)
{
     if(st==dr)
     {
               arb[nod]=value;
               return;
     }
     int mij=(st+dr)/2;
     if(index<=mij)
                   UpdateArb(nod*2,st,mij);
     else
                   UpdateArb(nod*2+1,mij+1,dr);
     arb[nod]=arb[nod*2]+arb[nod*2+1];        
}

void QueryArb(int nod,int st,int dr,int s)
{
    if(st==dr)
    {
             index=st;
             return;
    }
    int mij=(st+dr)/2;
    if(arb[nod*2]>=s)
    QueryArb(nod*2,st,mij,s);
    else
    QueryArb(nod*2+1,mij+1,dr,s-arb[nod*2]);
}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
                    scanf("%d",&poz_i[i]); 
                    index=i;value=1;
                    UpdateArb(1,1,n);
    }
    value=0;
    for(i=n;i>=1;i--)
    {
                     QueryArb(1,1,n,poz_i[i]);
                     poz_f[index]=i;
                     UpdateArb(1,1,n);
    }
    for(i=1;i<=n;i++)
    printf("%d\n",poz_f[i]);
    return 0;
}