Cod sursa(job #211665)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 3 octombrie 2008 10:45:51
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
# include <cstdio>

using namespace std;

# define FIN "schi.in"
# define FOUT "schi.out"
# define MAXN 30005

int N,i;
int Tree[3*MAXN];
int C[MAXN];
int L[MAXN];

    void update(int nod,int st,int dr)
    {
        int mij;
       
        if (st == dr)
          Tree[nod] = 1;
        else
          {
             mij = (st + dr) >> 1;
             update(nod<<1,st,mij);
             update(nod<<1|1,mij+1,dr);
             Tree[nod] = Tree[nod<<1] + Tree[nod<<1|1];
          }
    }
    
    void query(int nod,int st,int dr,int con,int poz)
    {
        int mij;
        
        if (st == dr)
          {
             L[st] = con;
             Tree[nod]--;
          }
        else
          {
             mij = (st + dr) >> 1;
             if (poz <= Tree[nod<<1])
               query(nod<<1,st,mij,con,poz);
             else
               query(nod<<1|1,mij+1,dr,con,poz-Tree[nod<<1]);
             Tree[nod] = Tree[nod<<1] + Tree[nod<<1|1];
          }
    }

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%d",&N);
        for (i = 1; i <= N; ++i)
          scanf("%d",&C[i]);
        
        update(1,1,N);
        
        for (i = N; i >= 1; --i)
          query(1,1,N,i,C[i]);
          
        for (i = 1; i <= N; ++i)
          printf("%d\n",L[i]);
        
        return 0;
    }