TopCoder

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

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

42.7% (32/75)

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

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