MSE07B - Double Queue
Tác giả: RR
Ngôn ngữ: Pascal
//Written by Nguyen Thanh Trung
{$R+,Q+}
{$Mode objFPC}
const
FINP='';
FOUT='';
MAXN=1000001;
oo=1000000000;
procedure swap(var a,b:longint);
var temp:longint;
begin temp:=a; a:=b; b:=temp; end;
type
heap=object
hmin,hmax,inmin,inmax,vmin,vmax:array[1..MAXN] of longint;
hminsize,hmaxsize:longint;
procedure downMax(i:longint);
procedure downMin(i:longint);
procedure upMax(i:longint);
procedure upMin(i:longint);
procedure push(u,k:longint);
procedure popMax(var u,k:longint);
procedure popMin(var u,k:longint);
end;
procedure heap.downMax(i:longint);
var
j:longint;
begin
j:=i<<1;
while (j<=hmaxsize) do
begin
if (j<hmaxsize) and (hmax[j+1]>hmax[j]) then inc(j);
if (hmax[j]>hmax[i]) then
begin
swap(inmax[inmin[i]],inmax[inmin[j]]);
swap(inmin[i],inmin[j]);
swap(hmax[i],hmax[j]);
swap(vmax[i],vmax[j]);
end;
i:=j; j:=i<<1;
end;
end;
procedure heap.downMin(i:longint);
var
j:longint;
begin
j:=i<<1;
while (j<=hminsize) do
begin
if (j<hminsize) and (hmin[j+1]<hmin[j]) then inc(j);
if (hmin[j]<hmin[i]) then
begin
swap(inmin[inmax[i]],inmin[inmax[j]]);
swap(inmax[i],inmax[j]);
swap(hmin[i],hmin[j]);
swap(vmin[i],vmin[j]);
end;
i:=j; j:=i<<1;
end;
end;
procedure heap.upMax(i:longint);
var
j:longint;
begin
j:=i>>1;
while (i>1) and (hmax[i]>hmax[j]) do
begin
swap(inmax[inmin[i]],inmax[inmin[j]]);
swap(inmin[i],inmin[j]);
swap(hmax[i],hmax[j]);
swap(vmax[i],vmax[j]);
i:=j; j:=i>>1;
end;
end;
procedure heap.upMin(i:longint);
var
j:longint;
begin
j:=i>>1;
while (i>1) and (hmin[i]<hmin[j]) do
begin
swap(inmin[inmax[i]],inmin[inmax[j]]);
swap(inmax[i],inmax[j]);
swap(hmin[i],hmin[j]);
swap(vmin[i],vmin[j]);
i:=j; j:=i>>1;
end;
end;
procedure heap.push(u,k:longint);
begin
inc(hmaxsize); hmax[hmaxsize]:=u; vmax[hmaxsize]:=k;
inc(hminsize); hmin[hminsize]:=u; vmin[hminsize]:=k;
inmax[hminsize]:=hmaxsize; inmin[hmaxsize]:=hminsize;
upMax(hmaxsize); upMin(hminsize);
end;
procedure heap.popMax(var u,k:longint);
var
v:longint;
begin
u:=hmax[1]; k:=vmax[1];
v:=inmin[1]; hmin[v]:=-maxlongint; upMin(v);
swap(hmax[1],hmax[hmaxsize]);
swap(vmax[1],vmax[hmaxsize]);
swap(inmin[1],inmin[hmaxsize]);
inmax[inmin[1]]:=1; inmax[inmin[hmaxsize]]:=hmaxsize;
swap(hmin[1],hmin[hminsize]);
swap(vmin[1],vmin[hminsize]);
swap(inmax[1],inmax[hmaxsize]);
inmin[inmax[1]]:=1; inmin[inmax[hminsize]]:=hminsize;
dec(hminsize); downMin(1);
dec(hmaxsize); downMax(1);
end;
procedure heap.popMin(var u,k:longint);
var
v:longint;
begin
u:=hmin[1]; k:=vmin[1];
v:=inmax[1]; hmax[v]:=maxlongint; upMax(v);
swap(hmax[1],hmax[hmaxsize]);
swap(vmax[1],vmax[hmaxsize]);
swap(inmin[1],inmin[hmaxsize]);
inmax[inmin[1]]:=1; inmax[inmin[hmaxsize]]:=hmaxsize;
swap(hmin[1],hmin[hminsize]);
swap(vmin[1],vmin[hminsize]);
swap(inmax[1],inmax[hminsize]);
inmin[inmax[1]]:=1; inmin[inmax[hminsize]]:=hminsize;
dec(hminsize); downMin(1);
dec(hmaxsize); downMax(1);
end;
var
a:heap;
u,k,request:longint;
begin
// assign(input,'input.txt'); reset(input);
// assign(output,'output.txt'); rewrite(output);
read(request);
while request>0 do
begin
case request of
1: begin
read(k,u);
a.push(u,k);
end;
2: if a.hmaxsize=0 then writeln(0)
else
begin
a.popMax(u,k);
writeln(k);
end;
3: if a.hminsize=0 then writeln(0)
else
begin
a.popMin(u,k);
writeln(k);
end;
end;
read(request);
end;
// close(input); close(output);
end.