[Buổi 15][STL][HW] Bài 4: Kho khóa–giá trị theo lệnh

LÀM BÀI
Points: 100
Time limit: 1.0s
Memory limit: 256M
Author:
Mai_Dang_Huy_000000_FullHousedev
Problem types
Allowed languages
C++

Kho khóa–giá trị theo lệnh

Bối cảnh

Một dịch vụ cấu hình lưu các cặp id → value. Sau khi nạp trạng thái ban đầu, hệ thống nhận một chuỗi lệnh cập nhật và truy vấn. ADD id delta cộng delta vào value hiện tại; nếu id chưa tồn tại thì tạo mới với value=delta. SET id value gán tuyệt đối và cũng tạo mới nếu cần. GET id chỉ đọc, tuyệt đối không được vô tình tạo key. COUNT hỏi số key đang tồn tại, còn TOTAL hỏi tổng value của toàn bộ kho.

Nếu mỗi lệnh TOTAL lại duyệt toàn map để cộng, chương trình vẫn có thể chạy với dữ liệu nhỏ nhưng không phản ánh tư duy quản lý state tốt. Hãy duy trì thêm biến total và cập nhật nó đồng bộ với mỗi ADD/SET. Bài Medium yêu cầu hiểu side effect của map::operator[], phân biệt thao tác đọc và ghi, đồng thời bảo toàn invariant total = tổng value của mọi key sau mọi lệnh.

Yêu cầu

  1. Đọc n cặp id value ban đầu, id không trùng.
  2. Xử lý q lệnh ADD/SET/GET/COUNT/TOTAL.
  3. GET id không được tạo key mới.
  4. Duy trì total mà không quét lại toàn map ở mỗi lệnh TOTAL.
  5. In kết quả cho GET/COUNT/TOTAL.

Input

Dòng 1 n; n dòng id value; dòng q; q lệnh.

Output

Mỗi lệnh GET/COUNT/TOTAL tạo một dòng output.

Ràng buộc

0≤n,q≤5000, |id|≤10^9, mọi tổng nằm trong long long.

Ví dụ 1

Input

2
10 100
20 50
7
GET 10
ADD 20 25
TOTAL
SET 30 40
COUNT
GET 30
GET 99

Output

100
175
3
40
NOT_FOUND

Giải thích

Ban đầu kho có 10→100, 20→50, total=150. GET 10 in 100. ADD 20 25 đổi 20 thành 75 và total thành 175, nên TOTAL in 175. SET 30 40 tạo key mới, count thành 3 và total 215. GET 30 in 40; GET 99 không tồn tại nên NOT_FOUND và không làm count thay đổi.

Ví dụ 2

Input

0
6
COUNT
TOTAL
ADD 5 7
GET 5
SET 5 10
TOTAL

Output

0
0
7
10

Giải thích

Kho ban đầu rỗng nên COUNT và TOTAL lần lượt là 0. ADD 5 7 tạo key 5 với value 7, nên GET 5 in 7. SET 5 10 thay value cũ 7 bằng 10; total phải tăng đúng 3 chứ không cộng thêm 10, vì vậy TOTAL cuối cùng in 10.

Thông tin học tập

  • Module: M05
  • Buổi: B15
  • Loại bài: HOMEWORK
  • Độ khó: Medium
  • Concepts: map, key-value updates, find, aggregate state, command simulation
  • Giới hạn kiến thức: B01-B15
  • Time limit: 1 second(s)
  • Memory limit: 256 MB
  • Point: 100

Comments

There are no comments at the moment.

Zalo