Cod sursa(job #338428)

Utilizator rumburakrumburak rumburak Data 5 august 2009 19:28:34
Problema Schi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<cstdio>

const int N = (1<<15);

int v[N],poz[N],n,t[N<<2],a,b;

void citire()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&v[i]);
}

int query(int p,int st,int dr)
{
	if(a<=st && dr<=b)
		return t[p];
	int mid=(st+dr)>>1;
	if(a<=mid)
		return t[p]+query(p<<1,st,mid);
	else
		return t[p]+query((p<<1)+1,mid+1,dr);
}

void update(int p,int st,int dr)
{
	if(a<=st && dr<=b)
	{
		++t[p];
		return;
	}
	int mid=(st+dr)>>1;
	if(a<=mid)
		update(p<<1,st,mid);
	if(b>mid)
		update((p<<1)+1,mid+1,dr);
}

void calcul()
{
	int i,q,r;
	for(i=n;i;--i)
	{
		r=v[i];
		do{
			a=b=v[i];
			q=query(1,1,n);
			r+=q;
		}while(poz[r]);
		poz[r]=i;
		b=n;
		update(1,1,n);
	}
}

void scrie()
{
	for(int i=1;i<=n;++i)
		printf("%d\n",poz[i]);
}

int main()
{
	freopen("schi.in","r",stdin);
	freopen("schi.out","w",stdout);
	citire();
	calcul();
	scrie();
	return 0;
}