Seletiva IOI 2013

codreverso_treap.cpp

// Ivan Carvalho
// Código Reverso - Seletiva IOI - OBI 2013
// Alternative solution : O(n*lg(n))
#include <bits/stdc++.h>
typedef struct node* pnode;
const int MAXN = 500010;
int entrada[MAXN],resposta[MAXN],N;
struct node{
	int key,prior,size;
	pnode l,r;
	node(int key) : key(key), prior(rand()), size(1), l(NULL), r(NULL) {}
};
int sz(pnode t){
	if(t == NULL) return 0;
	return t->size;
}
void upd_sz(pnode t){
	if(t == NULL) return;
	t->size = sz(t->l) + 1 + sz(t->r);
}
void split(pnode t,int key,pnode &l,pnode &r){
	if(t == NULL){
		l = r = NULL;
	}
	else if(key < t->key){
		split(t->l,key,l,t->l);
		r = t;
	}
	else{
		split(t->r,key,t->r,r);
		l = t;
	}
	upd_sz(t);
}
void merge(pnode &t,pnode l,pnode r){
	if(l == NULL){
		t = r;
	}
	else if(r == NULL){
		t = l;
	}
	else if(l->prior > r->prior){
		merge(l->r,l->r,r);
		t = l;
	}
	else{
		merge(r->l,l,r->l);
		t = r;
	}
	upd_sz(t);
}
void insert(pnode &t,int key){
	pnode aux = new node(key);
	pnode L,R;
	split(t,key,L,R);
	merge(t,L,aux);
	merge(t,t,R);
}
void erase(pnode &t,int key){
	pnode L,R,mid;
	split(t,key-1,L,R);
	split(R,key,mid,R);
	merge(t,L,R);
}
int kth(pnode t,int k){
	int davez = sz(t->l) + 1;
	if(k == davez) return t->key;
	if(k < davez) return kth(t->l,k);
	return kth(t->r,k - davez);
}
int main(){
	scanf("%d",&N);
	pnode raiz = NULL;
	for(int i=1;i<=N;i++){
		insert(raiz,i);
		scanf("%d",&entrada[i]);
	}
	for(int i = N;i>=1;i--){
		int k = i - entrada[i];
		int resp = kth(raiz,k);
		resposta[i] = resp;
		erase(raiz,resp);
	}
	for(int i=1;i<=N;i++) printf("%d ",resposta[i]);
	printf("\n");
	return 0;
}