TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

88.9% (8/9)

Submission's AC Ratio

43.7% (38/87)

Description

「不管遇上什麼問題,一顆炸彈總能解決你的困擾——如果不行就兩顆。解決不了問題那是你當量不夠,這是普世真理。」

當今的帝國審查官兼諸界巡視者暨煉獄星領主——郝仁,在去找女神渡鴉12345 蹭飯的路上遇到一群不⻑眼的史萊姆擋路,江湖人稱炸彈超仁的他決定扔炸彈開路。

擋路的史萊姆們巧妙地排成了一個$n\times m$ 的格狀陣型。其中郝仁視角中左上角那格的座標為$(1, 1)$,右下角為$(n, m)$。每格中可能有若干隻史萊姆直直向上疊起來,也有可能一格內所有史萊姆都被嚇跑了,導致該格一隻史萊姆也沒有。

郝仁打算依序扔$q$ 顆炸彈來趕走史萊姆。第$i$ 顆炸彈會落於座標$(x_i, y_i)$ 的格子正中央,其爆炸半徑為$r_i$。而當第$i$ 顆炸彈落下後,所有座標$(x, y)$滿足$(x - x_i)^ 2 + (y - y_i)^ 2 \leq r_i^ 2$的非空格子中,最上面的那隻史萊姆會被炸彈嚇跑。

身為一個專業的炸彈仁,忠實紀錄每顆炸彈的威力是他的職責所在。對於每顆炸彈,郝仁想要知道它嚇跑了幾隻史萊姆。但是史萊姆實在太多了,希望你可以寫個程式幫幫他。

Input Format

測試資料第一行有三個整數$n, m, q$,分別代表史萊姆陣型的⻑與寬,以及炸彈的數量。接下來$n$ 行,每行有$m$ 個字元,依序代表左上到右下每格包含的史萊姆數量。為了節省空間,郝人偷懶的使用了縮寫來記錄史萊姆數量。其中字元09 代表$0$ 到$9$ 隻史萊姆、字元az代表$10$ 到$35$ 隻史萊姆、字元AZ 則代表$36$ 到$61$ 隻史萊姆。接下來$q$ 行,每行有三個數字$x_i, y_i, r_i$,依序代表每顆炸彈的落點座標以及爆炸半徑。

  • $1\leq n, m\leq 1000$
  • $1\leq q \leq 100000$
  • $1\leq x_i \leq n$
  • $1\leq y_i \leq m$
  • $1\leq r_i \leq 5000$
  • 每格中的史萊姆數量不超過62 隻

Output Format

請輸出$q$ 行,每行包含一個整數。第$i$ 行中的數字表示第$i$ 顆炸彈嚇跑了幾隻史萊姆。

Sample Input

Sample Input #1
2 3 3
240
222
1 1 2
2 3 2
1 2 3

Sample Input #2
2 4 10
np5c
6es7
1 3 0
2 1 1
1 3 1
2 4 2
1 1 4
2 3 3
2 3 1
1 4 0
1 3 0
1 4 4

Sample Output

Sample Output #1
4
4
3

Sample Output #2
1
3
4
5
8
8
3
1
0
7

Hints

Problem Source

2017 NPSC高中組決賽

Subtasks

No. Testdata Range Score
1 0~30 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 6000 262144 262144 1
1 6000 262144 262144 1
2 6000 262144 262144 1
3 6000 262144 262144 1
4 6000 262144 262144 1
5 6000 262144 262144 1
6 6000 262144 262144 1
7 6000 262144 262144 1
8 6000 262144 262144 1
9 6000 262144 262144 1
10 6000 262144 262144 1
11 6000 262144 262144 1
12 6000 262144 262144 1
13 6000 262144 262144 1
14 6000 262144 262144 1
15 6000 262144 262144 1
16 6000 262144 262144 1
17 6000 262144 262144 1
18 6000 262144 262144 1
19 6000 262144 262144 1
20 6000 262144 262144 1
21 6000 262144 262144 1
22 6000 262144 262144 1
23 6000 262144 262144 1
24 6000 262144 262144 1
25 6000 262144 262144 1
26 6000 262144 262144 1
27 6000 262144 262144 1
28 6000 262144 262144 1
29 6000 262144 262144 1
30 6000 262144 262144 1