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
2016-06-04 10:47:45 Lê Trần Hữu Ðắc
sau n` lần thử sub vs n` giới hạn khác nhau, e rút ra 1 kết luận số thao tác 1 <= 9*10^4 =D
2016-05-23 09:31:53
dễ =)))
2015-06-22 19:21:29 The Flash
TLE mãi nản không tả được
2015-03-18 06:22:33 Con Bò Huyền Thoại


Last edit: 2017-08-20 18:35:20
2014-12-26 02:58:25 Con Bò Huyền Thoại
nếu học ko kỹ về heap, bạn sẽ ảo tưởng sức mạnh của nó :v mình đã thử và thất bại =))
2014-10-15 09:41:57 ??? Ares
code 2 Heap bên pascal bị SIGSEGV , sau 2 ngày mày mò về set bên C++ cũng AC :)) nhờ bài này mà biết thêm về set :v
2014-06-27 17:12:07 Anh Duc Le
mình làm priority queue vẫn AC mà :|
2014-06-27 16:12:23 Lollipop
Code mãi ms AC, phê
2014-06-27 11:10:53 Lollipop
sao lại ra 100
100

phai ra 100 0 chứ
2013-11-10 10:34:32 WAF|Tommy
Bài này rất dễ hiểu sai đề. Những ai bị sai thì nên thử test này:
1 100 10
1 100 35
2
3

và kết quả là:
100
100
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.