Tra cứu và thứ hạng theo ID

Bối cảnh

Một bảng điểm có n thí sinh, mỗi thí sinh có ID duy nhất và score. Hệ thống cần phục vụ ba loại truy vấn: FIND id trả score; RANK id trả rank 1-based sau khi xếp score giảm dần, tie ID tăng; TOP k trả thí sinh ở rank k.

Một representation duy nhất không thuận tiện cho cả ba workload. map<id,score> phù hợp lookup; vector<pair<score,id>> phù hợp ranking; sau khi sort, thêm map<id,rank> giúp trả rank O(log n) mà không scan vector. Bài Medium của B18 nhấn mạnh tư duy xây nhiều state nhất quán từ cùng nguồn dữ liệu, thay vì ép map hoặc vector làm mọi việc.

Nếu chỉ có một vài query, ta có thể scan ranking để tìm ID, nhưng với hàng nghìn query việc đó biến thành O(nq). Bài yêu cầu chuẩn bị index từ trước: sau khi ranking ổn định, mỗi ID được ánh xạ sang rank đúng một lần. Đây là ví dụ nhỏ của kỹ thuật "precompute index" thường dùng trong hệ thống tra cứu và các bài offline query.

Yêu cầu

1. Đọc n cặp id score.
2. Build map lookup và vector ranking.
3. Sort score giảm; tie id tăng; build map id→rank.
4. Xử lý FIND/RANK/TOP.
5. ID không tồn tại trong FIND/RANK in NOT_FOUND.

Input

Dòng 1 n; n dòng id score; dòng q; q command.

Output

Mỗi query một dòng.

Ràng buộc

1≤n,q≤5000, ID duy nhất, TOP k hợp lệ.

Ví dụ 1

Input

4
10 90
20 95
30 95
40 80
6
FIND 30
RANK 30
RANK 20
TOP 1
TOP 3
FIND 99

Output

95
2
1
20 95
10 90
NOT_FOUND

Giải thích

Ranking là score 95 trước, tie ID nhỏ: ID20 rank1, ID30 rank2; tiếp theo ID10/90 rank3 và ID40/80 rank4. FIND 30 trả 95; RANK 30 trả 2; RANK 20 trả 1; TOP 1 là 20 95; TOP 3 là 10 90; ID99 không có nên NOT_FOUND.

Ví dụ 2

Input

1
7 42
4
FIND 7
RANK 7
TOP 1
RANK 8

Output

42
1
7 42
NOT_FOUND

Giải thích

Chỉ có ID7 score42, nên map lookup trả 42, map rank trả 1 và TOP1 cũng là 7 42. Query RANK8 không tìm thấy trong rankOf, vì vậy in NOT_FOUND mà không làm thay đổi dữ liệu.

Thông tin học tập

• Module: M05
• Buổi: B18
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: map lookup, vector pair, custom comparator, rank map, multiple representations
• Giới hạn kiến thức: B01-B18
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100