记录编号	338042	评测结果	AAAATAAAAT
题目名称	[HZOI 2016] 简单的Treap	最终得分	80
用户昵称	NewBee	是否通过	未通过
代码语言	C++	运行时间	7.247 s
提交时间	2016-11-05 07:22:59	内存使用	7.13 MiB

#include<cstdio>
#include<cstdlib>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("treap.in","r",stdin);freopen("treap.out","w",stdout);chul();Cu
using namespace std;
const int maxn=500010;
struct op{
	int key,fre,ls,rs;
}r[maxn];
int righ(int rt){
	int rx=rt;
	rt=r[rt].rs;
	r[rx].rs=r[rt].ls;
	r[rt].ls=rx;
	return rt;
}
int left(int rt){
	int rx=rt;
	rt=r[rt].ls;
	r[rx].ls=r[rt].rs;
	r[rt].rs=rx;
	return rt;
}
int merge(int rt,int x){
	if(r[x].key<r[rt].key){
		if(!r[rt].ls){
			r[rt].ls=x;
		}
		else{
			r[rt].ls=merge(r[rt].ls,x);
		}
		if(r[rt].fre>r[r[rt].ls].fre){
			rt=left(rt);
		}
	}
	else{
		if(!r[rt].rs){
			r[rt].rs=x;
		}
		else {
			r[rt].rs=merge(r[rt].rs,x);
		}
		if(r[rt].fre>r[r[rt].rs].fre){
			rt=righ(rt);
		}
	}	
	return rt;
}		
void dfs(int rt){
	printf("%d ",r[rt].key);
	if(r[rt].ls){
		dfs(r[rt].ls);
	}
	if(r[rt].rs){
		dfs(r[rt].rs);
	}
}			 
void chul(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&r[i].key);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&r[i].fre);
	}
	int rt=1;
	for(int i=2;i<=n;i++){
		rt=merge(rt,i);
	}
	dfs(rt);
}
int main(){
	int __size__=128<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	Begin;
}