Hàng đợi ưu tiên tự cài đặt
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Hãy tự cài đặt cấu trúc dữ liệu MinHeap bằng struct (không dùng std::priority_queue) để quản lý các công việc Task { int priority, id; }. Thực hiện $Q$ thao tác:
ADD id p: thêm công việc có mãidvà độ ưu tiênp(số nhỏ hơn ưu tiên cao hơn).POP: lấy ra và inidcủa công việc có độ ưu tiên cao nhất (nếu cùngp, chọnidnhỏ hơn). Nếu hàng đợi rỗng inEMPTY.
Dữ liệu vào
Dòng đầu chứa số nguyên $Q$.
$Q$ dòng tiếp theo, mỗi dòng là một lệnh ADD id p hoặc POP.
Dữ liệu ra
Với mỗi lệnh POP, in kết quả trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 5 ADD 101 5 ADD 102 2 ADD 103 2 POP POP |
102 103 |
| 2 POP ADD 1 1 |
EMPTY |
Giới hạn
- $1 \le Q \le 50000$
- $1 \le id, p \le 10^9$
Community Discussion