Hàng đợi ưu tiên tự cài đặt

Buổi 07 — Struct & File I/O Data-structures
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề 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ã id và độ ưu tiên p (số nhỏ hơn ưu tiên cao hơn).
  • POP: lấy ra và in id của công việc có độ ưu tiên cao nhất (nếu cùng p, chọn id nhỏ hơn). Nếu hàng đợi rỗng in EMPTY.
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$
Draft saved