MSE07B - Double Queue

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mse07b


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 

Được gửi lên bởi:~!(*(@*!@^&
Ngày:2009-04-12
Thời gian chạy:0.200s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Southeastern European 2007

hide comments
2009-05-27 07:45:22 Taylor Swift
use two heaps.



Last edit: 2009-05-27 07:45:53
2009-04-26 01:30:37 Trung Hiếu
anh minh chỉ comment cho mọi người tìm hiểu thêm về min-max heap thôi.có nhiều người chưa biết về cái đó mà
2009-04-25 15:51:38 Thiêm Nguyễn
bài này khó thế :( zzzzz
2009-04-25 13:08:23 Ku dở hơi!!!
bài này tutorial mà, đọc cái nhìn ngay ra cách làm, làm gì bạn phải nóng thế ^^
2009-04-24 13:12:56 Dao Bui Trung Kien
anh có cần phải set bài lên xong thì comment luôn cách làm không nhỉ ??
2009-04-23 15:39:28 ~!(*(@*!@^&
uh, MIN-MAX heap nghia la heap ho tro ca tim min va tim max chu ko phai 2 heap rieng re, va phai tu cai; con dung C++ thi dung STL tien hoi nen anh ghi MIN-MAX heap (PASCAL) :D - de gay nham lan
2009-04-23 10:51:06 RR
Cau "co the tim hieu MIN-MAX heap (Pascal)" nghia la sao a? Em tuong la trong pascal phai tu cai phan nay chu?
2009-04-22 17:25:31 ~!(*(@*!@^&
co the tim hieu MIN-MAX heap (Pascal)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.