Cộng hình chữ nhật trên bảng

Arrays Buổi 15 — Prefix Sum & Difference Array Buổi 69-70 — Mock Tổng hợp prefix-sum
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một bảng số kích thước $N \times M$ ban đầu tất cả các ô đều bằng $0$. Có $Q$ phép biến đổi, mỗi phép cho $(r_1, c_1, r_2, c_2, v)$: cộng thêm giá trị $v$ vào tất cả các ô $(i, j)$ thỏa mãn $r_1 \le i \le r_2$ và $c_1 \le j \le c_2$. Sau $Q$ phép biến đổi, hãy tìm giá trị lớn nhất trong bảng.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $N, M, Q$.
  • $Q$ dòng tiếp theo, mỗi dòng chứa năm số nguyên $r_1, c_1, r_2, c_2, v$.
Dữ liệu ra

In ra một số nguyên duy nhất là giá trị lớn nhất trong bảng sau $Q$ phép biến đổi.

Ví dụ
Input Output
3 3 2
1 1 2 2 5
2 2 3 3 3
8
Giới hạn

$1 \le N, M \le 1000$, $1 \le Q \le 10^5$, $|v| \le 10^9$.

Draft saved