Leaderboard Analytics

Bối cảnh

Một leaderboard cần vừa xếp hạng vừa trả lời nhanh tổng score theo khoảng rank.

Pipeline bắt buộc: comparator → sort → prefix trên đúng state ranking.

Yêu cầu

1. Đọc n {score,id}.
2. Sort score giảm, tie id tăng.
3. Build prefix score sau sort.
4. Query RANK k: in id score ở rank 1-based.
5. Query SUM L R: in tổng score rank L..R.

Yêu cầu tổ chức code

Phải dùng pair, custom comparator strict và prefix n+1; không dùng struct.

Online Judge chấm output. Với bài nhạy về cấu trúc lời giải, giảng viên có thể review source code để xác nhận học viên luyện đúng năng lực.

Input

Dòng 1 n; n dòng score id; dòng tiếp q; q dòng RANK k hoặc SUM L R.

Output

Mỗi query một dòng.

Ràng buộc

1≤n,q≤5000, rank hợp lệ.

Ví dụ 1

Input

5
90 3
95 7
95 2
80 1
70 5
5
RANK 1
RANK 3
SUM 1 2
SUM 2 4
RANK 5

Output

2 95
3 90
190
265
5 70

Giải thích

Comparator tạo ranking: (95,id2), (95,id7), (90,id3), (80,id1), (70,id5). Prefix score được build sau ranking nên SUM 1 2 = 190 và SUM 2 4 = 95+90+80 = 265. RANK 1 trả ID 2/95, RANK 3 trả ID 3/90, RANK 5 trả ID 5/70. Nếu prefix được build trước sort, các tổng theo rank sẽ sai.

Ví dụ 2

Input

1
10 9
3
RANK 1
SUM 1 1
RANK 1

Output

9 10
10
9 10

Giải thích

Với một record (score=10,id=9), ranking có đúng rank 1 và prefix là pre[0]=0, pre[1]=10. RANK 1 trả 9 10. Query SUM 1 1 lấy pre[1]-pre[0]=10, rồi RANK 1 lần nữa vẫn trả cùng record. Vì chỉ có một state, mọi phép tra cứu và tổng đều phải nhất quán.

Thông tin học tập

• Module: M05
• Buổi: B17
• Loại bài: WORKSHOP
• Độ khó: Hard
• Concepts: pair, custom comparator, ranking, prefix sum, rank query
• Giới hạn kiến thức: B01-B17
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100