Treap - WA9 #2

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

uses
    SysUtils, Math;

type
    PE = ^TE;
    TE = record
        x,y,n:longint;
        l,r,p:PE;
    end;

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


procedure Init(var root:PE);
begin
root := nil;
end;

procedure Split(pt : PE; key : longint; var pL, pR : PE);
begin
if pt = nil then begin
    pL := nil;
    pR := nil;
end else
if pt^.x < x then begin
    pL := pt;
    Split(pL^.R, key, pL^.R, pR);
end else begin
    pR := pt;
    Split(pR^.L, key, pL, pR^.L);
end;
end;

procedure Add1(var p : PE; var np : PE; prev:PE);
begin
if p = nil then begin
    p := np;
    p^.p := prev;
end else
    if np^.y > p^.y then
        if np^.x = p^.x then exit else
        if np^.x < p^.x then Add1(p^.L, np, p) else Add1(p^.R, np, p)
    else begin
        Split(p, np^.x, np^.L, np^.R);
        p := np;
        p^.p := prev;
        if p^.l <> nil then p^.l^.p := p;
        if p^.r <> nil then p^.r^.p := p;
    end;
end;


procedure Add(var root : PE; x,y:longint);

var
    np : PE;

begin
new(np);
np^.x := x;
np^.y := y;
np^.n := i;
np^.l := nil;
np^.r := nil;
np^.p := nil;
Add1(root, np, nil);
a[i] := np;
end;

begin
reset(input, 'input.txt');
rewrite(output, 'output.txt');
read(n);
init(root);
for i := 1 to n do begin
    read(x, y);
    add(root, x, y);
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.