Cod sursa(job #1311618)

Utilizator BlackBird_v.1.0Stephen Berg BlackBird_v.1.0 Data 8 ianuarie 2015 13:59:29
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
#define Nmax 300013
int n,i,j,k;
int Stree[4*Nmax];
int a[Nmax],Sol[Nmax];

void update(int nod, int st,int dr, int x,int y,int value)
{
 if (st>dr || st>y || dr<x) return ;
 if (st==dr)
        {
         Stree[nod]=value;
         return ;
		}
 update(nod*2,st,(st+dr)/2,x,y,value);
 update(nod*2+1,(st+dr)/2+1,dr,x,y,value);
 Stree[nod]=Stree[nod*2]+Stree[nod*2+1];
}

int query(int nod,int st,int dr,int poz)
{
 if (st==dr) return dr;
 if (Stree[nod*2]>=poz) return query(nod*2,st,(st+dr)/2,poz);
 return query(nod*2+1,(st+dr)/2+1,dr,poz-Stree[nod*2]);
}

int main(void)
{
 in>>n;
 for (i=1;i<=n;++i)
	{
	 in>>a[i];
	 update(1,1,n,i,i,1);
	}
 for (i=n;i>=1;--i)
   {
   	int poz=query(1,1,n,a[i]);
   	update(1,1,n,poz,poz,0);
   	Sol[poz]=i;
   }
 for (i=1;i<=n;++i)	
   out<<Sol[i]<<"\n";
 return 0;
}