MSE07B - Double Queue
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
maxn=1000000;
var h,g,p,q,a,b:array[0..maxn] of longint;
n,m,i,x,y,z:longint;
procedure updatemin(x,y:longint);
var cha,con:longint;
begin
if q[x]=0 then
begin
inc(m); con:=m;
end
else con:=q[x];
cha:=con shr 1;
while (cha>0) and (y<b[cha]) do
begin
g[con]:=g[cha];
b[con]:=b[cha];
q[g[con]]:=con;
con:=cha;
cha:=con shr 1;
end;
g[con]:=x; q[x]:=con; b[con]:=y;
end;
procedure updatemax(x,y:longint);
var cha,con:longint;
begin
if p[x]=0 then
begin
inc(n); con:=n;
end
else con:=p[x];
cha:=con shr 1;
while (cha>0) and (y>a[cha]) do
begin
h[con]:=h[cha];
a[con]:=a[cha];
p[h[con]]:=con;
con:=cha;
cha:=con shr 1;
end;
h[con]:=x; p[x]:=con; a[con]:=y;
end;
procedure editmin(z:longint);
var cha,con,x,y:longint;
begin
x:=g[m]; y:=b[m]; b[m]:=0; g[m]:=0; dec(m);
if z>m then exit;
cha:=z; con:=z shl 1;
while con<=m do
begin
if (con<m) and (b[con+1]<b[con]) then inc(con);
if y<=b[con] then break;
g[cha]:=g[con];
b[cha]:=b[con];
q[g[cha]]:=cha;
cha:=con;
con:=cha shl 1;
end;
g[cha]:=x; q[x]:=cha; b[cha]:=y;
updatemin(x,y);
end;
procedure editmax(z:longint);
var cha,con,x,y:longint;
begin
x:=h[n]; y:=a[n]; a[n]:=0; h[n]:=0; dec(n);
if z>n then exit;
cha:=z; con:=z shl 1;
while con<=n do
begin
if (con<n) and (a[con+1]>a[con]) then inc(con);
if y>=a[con] then break;
h[cha]:=h[con];
a[cha]:=a[con];
p[h[cha]]:=cha;
cha:=con;
con:=cha shl 1;
end;
h[cha]:=x; p[x]:=cha; a[cha]:=y;
updatemax(x,y);
end;
begin
assign(input,fi); reset(input);
m:=0; n:=0;
while true do
begin
read(z);
if z=0 then break;
if z=1 then
begin
read(x,y);
updatemin(x,y);
updatemax(x,y);
end
else
begin
if z=2 then
begin
if n=0 then
begin
writeln(0); continue;
end;
x:=h[1];
end
else
begin
if m=0 then
begin
writeln(0); continue;
end;
x:=g[1];
end;
writeln(x);
editmin(q[x]);
q[x]:=0;
editmax(p[x]);
p[x]:=0;
end;
end;
close(input);
end.