记录编号	366789	评测结果	AAAATAAAAT
题目名称	[HZOI 2016] 简单的Treap	最终得分	80
用户昵称	@@@@	是否通过	未通过
代码语言	Pascal	运行时间	5.992 s
提交时间	2017-01-25 22:16:32	内存使用	11.61 MiB

type arr=record
l,r,w,rnd,cnt:longint;
end;
var
a:array[0..500100]of arr;
dl:array[0..500100]of longint;
i,n,dw,num,root:longint;
procedure r_rotate(var x:longint);
var y:longint;
begin
        y:=a[x].l;a[x].l:=a[y].r;a[y].r:=x;
        x:=y;
end;
procedure l_rotate(var x:longint);
var y:longint;
begin
        y:=a[x].r;a[x].r:=a[y].l;a[y].l:=x;
        x:=y;
end;
procedure ins(var now:longint;i:longint);
var p:longint;
begin
        p:=a[i].w;
        if now=0 then begin now:=i;a[i].cnt:=1;exit;end;
        if p<a[now].w then
                begin
                        ins(a[now].l,i);
                        if a[a[now].l].rnd<a[now].rnd then r_rotate(now);
                        exit;
                end;
        ins(a[now].r,i);
        if a[a[now].r].rnd<a[now].rnd then l_rotate(now);
end;

procedure dfs(x:longint);
var i:longint;
begin
        if x=0 then exit;
        write(a[x].w,' ');
        dfs(a[x].l);
        dfs(a[x].r);
end;
begin
assign(input,'treap.in');
assign(output,'treap.out');
reset(input);
rewrite(output);
read(n);
for i:=1 to n do read(a[i].w);
for i:=1 to n do read(a[i].rnd);
for i:=1 to n do
ins(root,i);
dfs(root);
close(input);
close(output);
end.