Cod sursa(job #760498)

Utilizator ion824Ion Ureche ion824 Data 21 iunie 2012 17:24:54
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<fstream>
using namespace std;
struct {
       int pozl,conc;
       }A[65000];
int b[30005],poz,val;
ofstream fout("schi.out");  
     
void init(int nod,int left,int right){
        A[nod].pozl=right-left+1;
        if(left==right)return ;
        int div=(left+right)>>1;
        init(2*nod,left,div);
        init(2*nod+1,div+1,right);       
     }
       
void update(int nod,int left,int right,int pp){
     if(left==right){
       A[nod].pozl=0;
       A[nod].conc=val;
       return ;
                     }
     int div=(left+right)>>1;
     if(poz<=pp+A[2*nod].pozl)update(2*nod,left,div,pp);
                         else update(2*nod+1,div+1,right,pp+A[2*nod].pozl);
     A[nod].pozl=A[2*nod].pozl+A[2*nod+1].pozl;                      
     }
     
void write(int nod,int left,int right){
     if(left==right){
              fout<<A[nod].conc<<'\n';
              return ;
                } 
     int div=(left+right)>>1;
     write(2*nod,left,div);
     write(2*nod+1,div+1,right);
     }
       
int main(void){
    ifstream fin("schi.in");
    int n,i;
    fin>>n;
    for(i=1;i<=n;++i)fin>>b[i]; fin.close();
    init(1,1,n);
    for(i=n;i>0;--i)
    {
      poz=b[i]; val=i;             
      update(1,1,n,0);              
    }
    write(1,1,n);                                                        
 return 0;   
}