Cod sursa(job #145993)

Utilizator ProtomanAndrei Purice Protoman Data 29 februarie 2008 22:39:36
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#define mx 120010
long i,j,n,s;
long ai[mx];
long b[30010],a[30010];

void add(long nod, long p, long u, long poz)
{
	long m;
	if (p==u)
	{
		ai[nod]+=1;
		return;
	}
	if (p<u)
	{
		m=(p+u)/2;
		if (poz<=m)
			add(nod*2,p,m,poz);
		if (m<poz)
			add(nod*2+1,m+1,u,poz);
		ai[nod]=ai[2*nod]+ai[2*nod+1];
	}
}

void query(long nod, long p, long u, long a)
{
	long m;
	if (u<=a)
	{
		s+=ai[nod];
		return;
	}
	if (p<u)
	{
		m=(p+u)/2;
		if (a<=m)
			query(nod*2,p,m,a);
		if (a>m)
		{
			s+=ai[nod];
			query(nod*2+1,m+1,u,a);
		}
	}
}

int main()
{
	freopen("schi.in","r",stdin);
	freopen("schi.out","w",stdout);
	scanf("%ld",&n);
	for (i=1; i<=n; i++)
		scanf("%ld",&a[i]);
	for (i=n; i>0; i--)
	{
		s=0;
		query(1,1,n,a[i]);
		j=a[i]+s;
		while (b[j]!=0)
			j++;
		b[j]=i;
		add(1,1,n,a[i]);
	}
	for (i=1; i<=n; i++)
		printf("%ld\n",b[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}