Cod sursa(job #1235321)

Utilizator Kira96Denis Mita Kira96 Data 29 septembrie 2014 15:17:02
Problema Schi Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<fstream>
#define FOR(a,b,c) for(register int a=b;a<=c;++a)
#define ROF(a,b,c) for(register int a=b;a>=c;--a)
#define N 100100
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int n,x;
struct Tr
{
	Tr *l,*r;
	short int cnt,pr,val;
	Tr() {}
	Tr(short int _key,short int _pr,short int _val)
	{
		pr=_pr;
		val=_val;
		cnt=_key;
		l=r=NULL;
	}
};
#define T Tr*
T R;
int cnt(T t)
{
	if(!t)
		return 0;
	return t->cnt;
}
void upd(T &t)
{
	if(t)
	t->cnt=cnt(t->l)+cnt(t->r)+1;
}
void split(T t,T &l,T &r,int k,int add)
{
	if(!t)
		return void(l=r=NULL);
	int key=add+cnt(t->l)+1;
	if(k<=key)
		split(t->l,l,t->l,k,add),r=t;
	else
		split(t->r,t->r,r,k,key),l=t;
	upd(t);
}
void insert(T &t,T it,int add)
{
	if(!t)
		t=it;
	else
	if(it->pr > t->pr)
		split(t,it->l,it->r,it->cnt,add),t=it;
	else
	if(it->cnt<=add+cnt(t->l)+1)
		insert(t->l,it,add);
	else
		insert(t->r,it,add+cnt(t->l)+1);
	upd(t);
}
void dfs(T t)
{
	if(!t)
		return;
	dfs(t->l);
	g<<t->val<<"\n";
	dfs(t->r);
}
int main ()
{
	f>>n;
	FOR(i,1,n)
	{
		f>>x;
		T it=new Tr(x,rand()+1,i);
		insert(R,it,0);
	}
	dfs(R);
	return 0;
}