Trung tâm điều phối tích hợp

Bối cảnh và bài toán

Một trung tâm tính toán tiếp nhận các job từ nhiều hệ thống nội bộ. Mỗi job có id và priority. Vì một job đã xử lý không được phép gửi lại dưới cùng id, trung tâm phải lưu lịch sử tất cả id từng được chấp nhận. Đồng thời, trong các job còn chờ, trung tâm luôn phải chạy job có độ ưu tiên cao nhất.

Có ba loại lệnh:

• ADD id priority: nếu id đã từng được chấp nhận trước đây, kể cả job đó đã chạy xong, in DUPLICATE. Ngược lại in OK và đưa job vào hàng chờ.
• SEEN id: in YES nếu id đã từng được chấp nhận, ngược lại in NO.
• RUN: lấy và xóa job còn chờ có priority lớn nhất; nếu hòa, chọn id nhỏ hơn. In id; nếu không còn job chờ, in EMPTY.

Yêu cầu

Xử lý toàn bộ luồng lệnh, đồng thời bảo đảm đúng cả trạng thái lịch sử và trạng thái đang chờ.

Input

• Dòng 1: số lệnh q.
• q dòng tiếp theo là các lệnh.

Output

In phản hồi tương ứng cho mọi lệnh.

Ràng buộc

• 1 <= q <= 2 * 10^5
• 1 <= id, priority <= 10^9

Chấm điểm

Ví dụ 1

Input

8
ADD 5 10
ADD 2 10
SEEN 5
RUN
ADD 2 99
RUN
RUN
SEEN 7

Output

OK
OK
YES
2
DUPLICATE
5
EMPTY
NO

Giải thích. Hai job đầu cùng priority 10, nên id=2 chạy trước do nhỏ hơn. Sau khi job 2 đã chạy xong, lệnh ADD 2 99 vẫn bị từ chối vì id=2 nằm trong lịch sử đã chấp nhận.

Ví dụ 2

Input

4
RUN
SEEN 1
ADD 1 7
SEEN 1

Output

EMPTY
NO
OK
YES

Giải thích. Ban đầu chưa có job nên RUN trả EMPTY và SEEN 1 trả NO. Sau ADD 1 7, lịch sử đã chứa 1, vì vậy lần kiểm tra cuối trả YES.

Thông tin bài tập

• Yêu cầu ngoài OJ: nộp Decision Note theo template.

Nguồn: FULLHOUSE DEV — Self-generated.