a082. 彗星撞擊

題目描述

你正在研究一個有 R 橫列、C 直行的矩形區域，模擬恐龍棲息地與彗星撞擊事件。

地圖由 R × C 個格子組成，座標從 0 開始編號。格子 (r, c) 的橫列座標範圍為 0 ≤ r < R，直行座標範圍為 0 ≤ c < C。所有格子的初始地面高度都是 D。

地圖上有 K 隻恐龍，最初都處於清醒狀態。同一格可以有多隻恐龍，每隻都要分別計入數量。

接下來依序發生 M 次彗星撞擊。每次撞擊由中心座標 (a, b)、正方形邊長 S 及撞擊深度 d 定義，規則如下。

撞擊的影響範圍

S 一定是奇數。令 t = (S - 1) / 2，影響範圍包含所有符合下列條件的地圖格子：

• 橫列座標介於 a - t 與 a + t 之間，包含兩端。
• 直行座標介於 b - t 與 b + t 之間，包含兩端。

超出地圖邊界的部分不予處理。例如，S = 1 時只影響中心格；S = 3 時影響中心周圍的 3 × 3 正方形，再與地圖範圍取交集。

暈眩與地面凹陷

每次撞擊先判斷影響範圍內是否有清醒恐龍：

1. 有至少一隻清醒恐龍： 範圍內所有清醒恐龍都變為暈眩，這次撞擊不會降低任何格子的地面高度，即使其中有些格子沒有恐龍也一樣。
2. 沒有清醒恐龍： 範圍內每個格子的地面高度都減少 d。

暈眩的恐龍不會再次醒來，也不會阻止後續撞擊造成凹陷。撞擊造成的高度變化會累積，地面高度可以是負數。

請計算全部撞擊結束後的最高地面高度、最低地面高度，以及仍然清醒的恐龍隻數。

輸入格式

第一行有三個整數 R C D，表示地圖的橫列數、直行數與初始地面高度。

第二行有一個整數 K，表示恐龍數量。

接下來 K 行，每行有兩個整數 r_i c_i，表示第 i 隻恐龍的初始座標。若 K = 0，則沒有這些座標行。

接下來一行有一個整數 M，表示撞擊次數。

接下來 M 行，每行有四個整數 a_j b_j S_j d_j，依序表示第 j 次撞擊的中心座標、影響正方形邊長與撞擊深度。

限制

• 1 ≤ R, C, D ≤ 100
• 0 ≤ K ≤ 100
• 0 ≤ r_i < R，0 ≤ c_i < C
• 1 ≤ M ≤ 100
• 0 ≤ a_j < R，0 ≤ b_j < C
• 1 ≤ S_j ≤ 19，且 S_j 為奇數
• 1 ≤ d_j ≤ 10

子題

• 子題一（60 分）：R = 1。
• 子題二（40 分）：無額外限制。

輸出格式

輸出一行，包含三個整數，以空白分隔：

最高地面高度 最低地面高度 清醒恐龍隻數

清醒恐龍隻數是所有仍清醒的恐龍總數，不是有清醒恐龍的格子數量。

範例

範例輸入：

1 10 5
5
0 5
0 4
0 4
0 1
0 1
2
0 0 1 4
0 3 3 1

範例輸出：

5 1 3

範例說明

• 第一次撞擊只影響 (0, 0)，該格沒有清醒恐龍，因此高度由 5 降為 1。
• 第二次撞擊影響 (0, 2)、(0, 3)、(0, 4)。(0, 4) 的兩隻恐龍都變為暈眩，這三格的高度都維持 5。
• 最後最高高度是 5，最低高度是 1。(0, 1) 的兩隻恐龍與 (0, 5) 的一隻恐龍仍清醒，共 3 隻。

出處

2025 年 10 月 APCS 中級第一題。題意與範例參考 ZeroJudge r488：彗星撞擊。