MSE07B spoj – Double Queue

Nguồn đề bài: http://vn.spoj.com/problems/MSE07B/vn/

1. Đề bài MSE07B spoj

Ngân hàng BIG-Bank mở một chi nhánh ở Bucharest và được trang bị một máy tính hiện đại với các công nghệ mới nhập, C2#,VC3+ … chỉ chuối mỗi cái là không ai biết lập trình.

Họ cần một phần mềm mô tả hoạt động của ngân hàng như sau: mỗi khách hàng có một mã số là số nguyên K, và khi đến ngân hàng giao dịch, họ sẽ nhận được 1 số P là thứ tự ưu tiên của họ. Các thao tác chính như sau

0 Kết thúc phục vụ

1 K P Thêm khách hàng K vào hàng đợi với độ ưu tiên P

2 Phục vụ người có độ ưu tiên cao nhất và xóa khỏi danh sách hàng đợi

3 Phục vụ người có độ ưu tiên thấp nhất và xóa khỏi danh sách hàng đợi.

Tất nhiên là họ cần bạn giúp rồi.

Input

Mỗi dòng của input là 1 yêu cầu, và chỉ yêu cầu cuối cùng mới có giá trị là 0. Giả thiết là khi có yêu cầu 1 thì không có khách hàng nào khác có độ ưu tiên là P.

K<=10^6, và P<= 10^7.Một khách hàng có thể yêu cầu phục vụ nhiều lần và với các độ ưu tiên khác nhau.

Output

Với mỗi yêu cầu 2 hoặc 3, in ra trên 1 dòng mã số của khách hàng được phục vụ tương ứng. Nếu có yêu cầu mà hàng đợi rỗng, in ra số 0.

Sample

Input :
2
1 20 14
1 30 3
2
1 10 99
3
2
2
0
Ouput:
0
20
30
10
0

2. Code tham khảo MSE07B spoj

const   fi='';
        nmax=10000000;
type    data=longint;
        data1=record
                gt,vt:data;
        end;

var
        f:text;
        Heapmin,Heapmax:array[0..nmax+1] of data1;
        posmin,posmax:array[0..nmax+1] of data;
        nheapmin,nheapmax:data;

procedure swap(var a,b:data1);
var     c:data1;
begin
        c:=a;
        a:=b;
        b:=c;
end;

procedure upheapmin(i:data);
var     j:data;
begin
        if (i=1) or (heapmin[i].gt>=heapmin[i div 2].gt) then exit;

        posmin[heapmin[i].gt]:=i div 2;
        posmin[heapmin[i div 2].gt]:=i;

        swap(heapmin[i],heapmin[i div 2]);
        upheapmin(i div 2);
end;

procedure upheapmax(i:data);
begin
        if (i=1) or (heapmax[i].gt<=heapmax[i div 2].gt) then exit;
        posmax[heapmax[i].gt]:=i div 2;
        posmax[heapmax[i div 2].gt]:=i;
        swap(heapmax[i],heapmax[i div 2]);
        upheapmax(i div 2);
end;

procedure downheapmin(i:data);
var     j:data;
begin
        j:=i*2;
        if j>nheapmin then exit;
        if (j<nheapmin) and (heapmin[j+1].gt<heapmin[j].gt) then inc(j);
        if Heapmin[j].gt>=heapmin[i].gt then exit;
        posmin[heapmin[i].gt]:=j;
        posmin[heapmin[j].gt]:=i;
        swap(heapmin[i],heapmin[j]);
        downheapmin(j);
end;


procedure downheapmax(i:data);
var     j:data;
begin
        j:=i*2;
        if j>nheapmax then exit;
        if (j<nheapmax) and (heapmax[j+1].gt>heapmax[j].gt) then inc(j);
        if Heapmax[j].gt<=heapmax[i].gt then exit;
        posmax[heapmax[i].gt]:=j;
        posmax[heapmax[j].gt]:=i;
        swap(heapmax[i],heapmax[j]);
        downheapmax(j);
end;


procedure add(k,p:data);
begin
        inc(nheapmin);
        heapmin[nheapmin].gt:=p;
        heapmin[nheapmin].vt:=k;
        posmin [p]:=nheapmin;

        inc(nheapmax);
        heapmax[nheapmax].gt:=p;
        heapmax[nheapmax].vt:=k;

        posmax [p]:=nheapmax;

        upheapmax(nheapmax);
        upheapmin(nheapmin);
end;

function popmax(v:data):data1;
begin
        popmax:=heapmax[v];
        heapmax[v]:=heapmax[nheapmax];
        dec(nheapmax);
        posmax[heapmax[v].gt]:=v;
        upheapmax(v);
        downheapmax(v);
end;

Function PopMin (v : LongInt) : data1;
         Begin
              PopMin:=HeapMin[v];
              HeapMin[v]:=HeapMin[nHeapmin];
              dec(nHeapmin);
              PosMin[Heapmin[v].gt]:=v;
              UpheapMin(v);
              DownheapMin(v);
         end;


procedure docfile;
var     i,j,q,k,p:data;
        tmp:data1;
begin
        assign(f,fi); reset(f);
        nheapmin:=0;
        nheapmax:=0;
        repeat
                read(f,q);
                if q=0 then break;
                if q=1 then
                        begin
                                read(f,k,p);
                                add(k,p);
                        end
                else
                        if q=2 then
                                begin
                                        if nheapmax=0 then
                                                writeln(0)
                                        else
                                                begin
                                                        tmp:=popmax(1);
                                                        writeln(tmp.vt);
                                                        popmin(posmin[tmp.gt]);
                                                end;
                                end
                        else
                                begin
                                        if nheapmin=0 then
                                                writeln(0)
                                        else
                                                begin
                                                        tmp:=popmin(1);
                                                        writeln(tmp.vt);
                                                        popmax(posmax[tmp.gt]);


                                                end;
                                end;
        until false;
        close(f);
end;

begin
        docfile;
end.