Treap - WA9 #1

{$APPTYPE CONSOLE}
{$R+,S+,Q+,I+,O-}
{R-,S-,Q-,I-,O+}

uses
    SysUtils, Math;

type
    pnode=^node;
    node=record
        l,r,p:pnode;
        x,y,n:longint;
    end;

var
    i,n,x,y:longint;
    t,p,l,r:pnode;
    a:array[0..50010] of pnode;

procedure split(t:pnode; x:longint; var l,r:pnode);
begin
if t = nil then begin
    l := nil;
    r := nil;
end else
if x < t^.x then begin
    split(t^.l, x, l, r);
    t^.l := r;
    r := t;
end else begin
    split(t^.r, x, l, r);
    t^.r := l;
    l := t;
end;
end;

procedure insert(var t:pnode; x,y:longint; p:pnode);

var
    tmp:pnode;

begin
if (t = nil) or (y < t^.y) then begin
    new(tmp);
    split(t, x, tmp^.l, tmp^.r);
    t := tmp;
    t^.x := x;
    t^.y := y;
    t^.p := p;
    t^.n := i;
    if t^.l <> nil then t^.l^.p := t;
    if t^.r <> nil then t^.r^.p := t;
    a[i] := t;
end else
if x < t^.x then insert(t^.l, x, y, t) else insert(t^.r, x, y, t);
end;

begin
reset(input, 'input.txt');
rewrite(output, 'output.txt');
read(n);
t := nil;
for i := 1 to n do begin
    read(x, y);
    insert(t, x, y, nil);
end;
writeln('YES');
for i := 1 to n do begin
    p := a[i]^.p;
    if p = nil then write(0) else write(p^.n);
    write(' ');
    l := a[i]^.l;
    if l = nil then write(0) else write(l^.n);
    write(' ');
    r := a[i]^.r;
    if r = nil then write(0) else write(r^.n);
    writeln;
end;
end.