Cod sursa(job #1170835)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 14 aprilie 2014 18:05:27
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<fstream>
#define maxnod 65540//(1<<16)=65536
#define maxn 30005
using namespace std;
ifstream fi("schi.in");
ofstream fo("schi.out");

int suma[maxnod];
int i,n,a[maxn];
int poz,p[maxn];

void creare_arb(int nod,int st,int dr){
     if(st==dr) suma[nod]=1;
     else{
          int mid=(st+dr)/2;
          creare_arb(2*nod,st,mid);
          creare_arb(2*nod+1,mid+1,dr);
          suma[nod]=suma[2*nod]+suma[2*nod+1];
         }
}

void update(int nod,int st,int dr){
     if(st==dr){ p[dr]=i; suma[nod]=0; }
     else{
          int mid=(st+dr)/2;
          if(poz<=suma[2*nod]) update(2*nod,st,mid);
          else{ poz-=suma[2*nod]; update(2*nod+1,mid+1,dr); }
          suma[nod]=suma[2*nod]+suma[2*nod+1];
         }
}

int main(){
    fi>>n;
    for(i=1;i<=n;i++) fi>>a[i];
    
    creare_arb(1,1,n);
    
    for(i=n;i>0;i--){
                     poz=a[i];
                     update(1,1,n);
                    }
                     
    for(i=1;i<=n;i++) fo<<p[i]<<"\n";
    
    fi.close();
    fo.close();
    return 0;
}