Cod sursa(job #1389262)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 16 martie 2015 09:36:52
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <stdio.h>
int n;
int lib[30001],a[30001],arb[120001];
void updt(int s,int e,int val,int pos,int nod)
{
     if(s==e) arb[nod]=val;
     else
     {
         int mij=(s+e)/2;
         if(pos<=mij) updt(s,mij,val,pos,2*nod);
         else updt(mij+1,e,val,pos,2*nod+1);
         arb[nod]=arb[2*nod]+arb[2*nod+1];
     }
}
int query(int s,int e,int p1,int p2,int nod)
{
    if(s==p1&&e==p2) return arb[nod];
    else
    {
        int mij=(s+e)/2;
        if(p2<=mij) return query(s,mij,p1,p2,2*nod);
        else if(p1>mij) return query(mij+1,e,p1,p2,2*nod+1);
        else return (query(s,mij,p1,mij,2*nod)+query(mij+1,e,mij+1,p2,2*nod+1));
    }
}
int main()
{
    freopen ("schi.in","r",stdin);
    freopen ("schi.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
            scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++) updt(1,n,1,i,1);
    for(int j=n;j>=1;j--)
    {
            int s=1,e=n,poz;
            while(s<=e)
            {
                       int mij=(s+e)/2,v=query(1,n,1,mij,1);
                       if(v==a[j])
                       {
                                  poz=mij;
                                  e=mij-1;
                       }
                       else if(v<a[j]) s=mij+1;
                       else if(v>a[j]) e=mij-1;
            }
            lib[poz]=j;
            updt(1,n,0,poz,1);
    }
    for(int i=1;i<=n;i++) printf("%d\n",lib[i]);
}