Bảng điểm hai chiều

Buổi 67-68 — Mock IOI Data-structures
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề bài

Cho một bảng kích thước $N \times M$ ban đầu tất cả các ô đều có giá trị $0$. Có $Q$ truy vấn thuộc hai loại:

  • 1 x y v: cộng thêm $v$ vào ô $(x, y)$.
  • 2 x1 y1 x2 y2: tính tổng giá trị các ô $(x, y)$ thỏa mãn $x_1 \le x \le x_2$ và $y_1 \le y \le y_2$.

Dữ liệu vào

  • Dòng đầu chứa ba số nguyên $N, M, Q$ ($1 \le N, M \le 1000$, $1 \le Q \le 10^5$).
  • $Q$ dòng tiếp theo, mỗi dòng là một truy vấn 1 x y v ($1 \le x \le N, 1 \le y \le M, |v| \le 10^6$) hoặc 2 x1 y1 x2 y2 ($1 \le x_1 \le x_2 \le N, 1 \le y_1 \le y_2 \le M$).

Kết quả

Với mỗi truy vấn loại 2, in ra tổng tìm được trên một dòng.

Subtasks

  • Subtask 1 (25%): $N, M \le 50$, $Q \le 500$.
  • Subtask 2 (35%): $N, M \le 300$, $Q \le 10^4$.
  • Subtask 3 (40%): Không có ràng buộc thêm.

Ví dụ

Input Output
4 4 5
1 1 2 5
1 3 4 10
2 1 1 4 4
1 2 2 -3
2 1 2 3 3
15
2
Draft saved