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.

Download