Cod sursa(job #121482)

Utilizator megabyteBarsan Paul megabyte Data 8 ianuarie 2008 21:26:50
Problema Schi Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <cstdio>
//#include <algorithm>
#define INF "schi.in"
#define OUF "schi.out"
#define TMAX 65536
#define NMAX 30002
#define min(a,b) ((a<b)?(a):(b))
using namespace std;

short k[TMAX],bp[TMAX];
short n,a,b,val;

void k_insert(int nod,short st,short dr)
{
	if(a<=st&&dr<=b)
	{
		++k[nod];
	}
	else
	{
		short mij;
		mij=(st+dr)/2;
		if(a<=mij) k_insert(2*nod,st,mij);
		if(b>mij) k_insert(2*nod+1,mij+1,dr);
		++k[nod];
	}
}

short k_query(int nod,short st,short dr)
{
	if(a<=st&&dr<=b) return k[nod];
	else 
	{
		short mij,l,r;
		mij=(st+dr)/2;
		l=r=0;
		if(a<=mij) l=k_query(2*nod,st,mij);
		if(b>mij) r=k_query(2*nod+1,mij+1,dr);
		return l+r;
	}
}

void bp_insert(int nod,short st,short dr)
{
	if(a<=st&&dr<=b)
	{
		bp[nod]=val;
	}
	else
	{
		short mij,l,r;
		mij=(st+dr)/2;
		if(a<=mij) bp_insert(2*nod,st,mij);
		if(b>mij) bp_insert(2*nod+1,mij+1,dr);
		l=bp[2*nod];
		r=bp[2*nod+1];
		if(!l) l=NMAX;
		if(!r) r=NMAX;

		bp[nod]=min(l,r);
	}
}

short bp_query(int nod,short st,short dr)
{
	if(a<=st&&dr<=b) return bp[nod];
	else
	{
		short mij,l,r;
		mij=(st+dr)/2;
		l=r=NMAX;
		if(a<=mij) l=bp_query(2*nod,st,mij);
		if(b>mij) r=bp_query(2*nod+1,mij+1,dr);
		return min(l,r);
	}
}

int main()
{
	short i,v[NMAX],sol[NMAX];
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");

	fscanf(in,"%hd",&n);
	for(i=1;i<=n;++i) 
	{
		fscanf(in,"%hd",v+i);
		a=b=i;val=i;
		bp_insert(1,1,n);
	}
	//char ch;
	for(i=n;i>0;--i)
	{		
		a=1;b=v[i];
		val=k_query(1,1,n);//cate val au fost introduse in intervalul 1 v[i]
		a=v[i]+val;b=n;
		val=bp_query(1,1,n);//prima poz libera dupa a
		
		
		//printf("%hd",val);scanf("%c",&ch);

		a=v[i];b=v[i];
		k_insert(1,1,n);// intra v[i]
		sol[val]=i;
		a=val;b=val;val=NMAX;
		bp_insert(1,1,n);  //poz libera este eliminata
	}

	for(i=1;i<=n;++i) 
	{
		fprintf(out,"%hd\n",sol[i]);
		if(!sol[i]) sol[TMAX]=8;
	}
	fclose(in);fclose(out);
	return 0;
}