Danh mục sản phẩm

Bối cảnh

Mỗi sản phẩm có ID duy nhất và price. Hệ thống cần lookup theo ID, ranking theo price và tổng giá theo khoảng rank.

map và vector<pair> cùng tồn tại vì phục vụ hai workload khác nhau.

Yêu cầu

1. Đọc n id price; lưu map id→price và vector<pair<price,id>>.
2. Sort catalog price asc, tie id asc.
3. Build prefix price sau sort.
4. Query FIND id, ITEM k, hoặc RANGE L R (rank 1-based).

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

Không dùng struct, pointer hoặc OOP. Phải giải thích được trách nhiệm của map, vector<pair>, comparator và prefix.

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 id price; dòng q; q command.

Output

Mỗi query một dòng: price/NOT_FOUND, id price, hoặc tổng.

Ràng buộc

1≤n,q≤5000, ID duy nhất.

Ví dụ 1

Input

5
10 100
20 50
30 100
40 20
50 70
6
FIND 30
FIND 99
ITEM 1
ITEM 4
RANGE 1 3
RANGE 2 5

Output

100
NOT_FOUND
40 20
10 100
140
320

Giải thích

Map lưu id→price nên FIND 30 trả 100 còn ID 99 không có và in NOT_FOUND. Catalog sort theo price cho thứ tự (20,id40),(50,id20),(70,id50),(100,id10),(100,id30), nên ITEM 1 là 40 20, ITEM 4 là 10 100. Prefix trên catalog cho RANGE 1 3 = 140 và RANGE 2 5 = 320.

Ví dụ 2

Input

1
7 42
4
FIND 7
FIND 8
ITEM 1
RANGE 1 1

Output

42
NOT_FOUND
7 42
42

Giải thích

Với một sản phẩm id7 price42, map lookup chứa đúng cặp 7→42; catalog sort cũng chỉ có (42,id7) và prefix là 0,42. FIND 7 trả 42, FIND 8 là NOT_FOUND, ITEM 1 in 7 42, còn RANGE 1 1 bằng 42. Bốn kết quả khác nhau đều mô tả cùng một record và vì thế phải nhất quán.

Thông tin học tập

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