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.

Download