Điều phối tác vụ động

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

Một nền tảng tính toán duy trì danh sách các tác vụ đang chờ xử lý. Trong lúc hệ thống hoạt động, mức ưu tiên của một tác vụ có thể thay đổi; tác vụ cũng có thể bị hủy trước khi chạy. Đồng thời, bảng giám sát cần trả lời nhanh tác vụ nào đang quan trọng nhất và trạng thái hiện tại của một id bất kỳ.

Mỗi tác vụ có một id và một priority. Hệ thống hỗ trợ các lệnh:

• ADD id priority: thêm một tác vụ mới. Mỗi id chỉ xuất hiện trong lệnh ADD nhiều nhất một lần trong toàn bộ input.
• SET id priority: đổi mức ưu tiên của một tác vụ đang hoạt động.
• CANCEL id: hủy một tác vụ đang hoạt động.
• STATUS id: nếu tác vụ còn hoạt động, in priority hiện tại; ngược lại in INACTIVE.
• TOP: in id của tác vụ đang hoạt động có priority lớn nhất nhưng không xóa nó. Nếu không còn tác vụ, in EMPTY.
• RUN: in id của tác vụ đang hoạt động có priority lớn nhất rồi loại tác vụ đó khỏi hệ thống. Nếu không còn tác vụ, in EMPTY.

Nếu nhiều tác vụ có cùng priority, tác vụ có id nhỏ hơn được ưu tiên.

Các lệnh SET và CANCEL được đảm bảo chỉ áp dụng cho tác vụ đang hoạt động tại thời điểm đó.

Yêu cầu

Xử lý toàn bộ chuỗi lệnh và in đúng kết quả cho các lệnh STATUS, TOP và RUN.

Input

• Dòng 1: số lệnh q.
• q dòng tiếp theo: mỗi dòng là một lệnh theo một trong sáu dạng trên.

Output

Với mỗi lệnh STATUS, TOP hoặc RUN, in một dòng kết quả tương ứng.

Ràng buộc

• 1 <= q <= 2 * 10^5
• 1 <= id <= 10^9
• 1 <= priority <= 10^9
• Mỗi id xuất hiện trong ADD nhiều nhất một lần.

Chấm điểm

Ví dụ 1

Input

12
ADD 10 5
ADD 3 5
TOP
SET 10 20
TOP
STATUS 3
CANCEL 10
TOP
RUN
TOP
STATUS 3
STATUS 10

Output

3
10
5
3
3
EMPTY
INACTIVE
INACTIVE

Giải thích. Ban đầu 3 đứng trước 10 vì cùng priority 5 nhưng id nhỏ hơn. Sau SET 10 20, tác vụ 10 trở thành ưu tiên cao nhất. Khi 10 bị hủy, 3 lại đứng đầu; RUN loại 3, nên hệ thống trở thành rỗng.

Ví dụ 2

Input

10
ADD 7 100
SET 7 50
SET 7 100
ADD 2 100
TOP
RUN
TOP
RUN
TOP
STATUS 7

Output

2
2
7
7
EMPTY
INACTIVE

Giải thích. Một tác vụ có thể được cập nhật nhiều lần, kể cả quay lại mức ưu tiên cũ. Hệ thống vẫn phải bảo đảm mỗi id chỉ được xem là một tác vụ đang hoạt động với trạng thái mới nhất.

Thông tin bài tập

• Yêu cầu ngoài OJ: nộp Decision Note giải thích operation profile, baseline, các cấu trúc ứng viên và lý do chọn phương án cuối.

Nguồn: FULLHOUSE DEV — Self-generated.