a075. 暴雨與排水口

題目描述

城市用一張 R × C 的地圖記錄各處積水量。少數格子裝有排水口，每個排水口有剩餘容量；其餘格子沒有排水口。每個格子最多只有一個排水口，所有積水量一開始都不會是負數。這裡的排水口只攔截之後落下的新雨，不會抽走題目給定的初始積水，也不會清除之前累積的積水；因此有排水口的格子，積水量仍可能大於 0。

接下來依序發生 M 次降雨。每次降雨以左上角 (r1, c1)、右下角 (r2, c2) 指定一塊包含邊界的矩形，並帶來 d 單位的水。矩形內每個格子各自處理一次：若該格排水口目前剩餘容量大於 0，它吸收這次降雨、容量減少 1，積水量不變；否則積水量增加 d。降雨範圍之外的格子不受影響。

注意容量以降雨次數消耗，不是減去 d；同一次降雨即使帶來很多水，排水口也只消耗 1 容量。前一次降雨用盡容量後，下一次降雨就會使該格積水。請計算所有降雨結束後，整張地圖的最大積水量、最小積水量，以及排水口剩餘容量的總和。

規則圖解

每格只需判斷這次降雨是否淋到它，以及它的排水口當下是否還有容量：

條件	這格的積水量	這格的排水容量
不在降雨矩形內	不變	不變
在矩形內，容量大於 0	不變	減少 1
在矩形內，沒有排水口或容量為 0	增加 d	維持 0

「積水量不變」是指不增加新雨，也不減少原有的水。例如原本有 4 單位積水的格子，排水口仍有容量時被雨淋到，積水量依然是 4，不會變成 0。

範例一的初始地圖如下。星號表示有排水口；括號內是初始容量，星號不是輸入的一部分：

             c=0     c=1     c=2
r=0           2       1*(1)   3
r=1           0       4*(2)   2

三次降雨結束後，積水地圖為：

             c=0  c=1  c=2
r=0           4    2    5
r=1           2    4    4

初始時 (0, 1) 已有 1 單位積水，(1, 1) 已有 4 單位積水；即使兩格的排水口還有容量，這些水都不會消失。第一場雨覆蓋整張地圖，兩格排水口只攔截新雨；第二場雨只用掉 (1, 1) 剩下的一次容量；第三場雨讓已無容量的 (0, 1) 從 1 增至 2。兩個排水口最後容量都是 0。

輸入格式

依序讀入下列資料；同一行的整數以空白分隔：

1. 第一行：整數 R、C，分別是地圖的行數與列數。
2. 接下來 R 行：第 r 行有 C 個整數，依序為 (r, 0) 到 (r, C-1) 的初始積水量。
3. 下一行：整數 K，排水口數量；若 K=0，就沒有排水口資料行。
4. 接下來 K 行：r c capacity，表示位於 (r, c) 的排水口及初始容量。
5. 下一行：整數 M，降雨次數。
6. 接下來 M 行：r1 c1 r2 c2 d，依輸入順序降雨；包含四周邊界的矩形內每格都會受到這場雨影響。

所有座標從左上角 (0, 0) 起算，行號往下、列號往右增加。

限制

• 1 ≤ R, C ≤ 100；0 ≤ K ≤ R × C；1 ≤ M ≤ 100
• 初始積水量介於 0 到 1000；1 ≤ capacity, d ≤ 100
• 排水口座標互不相同；0 ≤ r1 ≤ r2 < R、0 ≤ c1 ≤ c2 < C

輸出格式

輸出一行，以空白隔開：最大積水量 最小積水量 剩餘容量總和。最大與最小值要比較整張地圖的所有格子（包含沒有被雨淋到的格子）；若沒有排水口，剩餘容量總和為 0。

範例1

範例輸入：

2 3
2 1 3
0 4 2
2
0 1 1
1 1 2
3
0 0 1 2 2
1 1 1 1 3
0 1 0 1 1

範例輸出：

5 2 0

(0, 1) 一開始就有 1 單位積水，第一場雨被排水口攔截後仍是 1；(1, 1) 原有的 4 單位積水也不會消失。第二場雨用盡 (1, 1) 的容量；第三場雨才使 (0, 1) 從 1 增加到 2。

範例2

範例輸入：

1 1
0
1
0 0 2
3
0 0 0 0 4
0 0 0 0 7
0 0 0 0 2

範例輸出：

2 2 0

前兩場雨由排水口吸收，第三場雨才使積水量變成 2。