TopCoder

Thumb head photo2
bb
師宇好可愛 - https://brian.su

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

50.0% (21/42)

Description

苦無 (Kunai) 是一個刀子形狀的尖銳武器,忍者會對他們的敵人投擲苦無。
現在有 N 名忍者在 H 列 W 行的方陣中,每名忍者在格子的正中央,並且一個格子不會有兩名以上的忍者。每名忍者都有一把苦無,並且面向上、下、左、右四個方向中的其中一個方向。在時間點 0 時,每名忍者朝他們面向的方向投擲出苦無。
每把苦無以速度 1 直線前進,如果有不止一把苦無在同一時間飛到同一地點,它們會破撞並且消失。我們可以忽略苦無的大小。另外,由於忍者可以快速移動,所以他們不會被苦無擊中。每把苦無會以等速直線飛行,除非和另外的苦無碰撞。
在下圖中,箭頭代表苦無,箭頭方向代表苦無飛行的方向,在這些圖中,所有粗體的箭頭都會發生碰撞。

而在下列圖中,粗箭頭並不會和另一個粗箭頭相撞。第二和第三張圖中,細箭頭會和一個粗箭頭相撞。因為相撞的箭頭會消失,因此這兩張圖中各有一個粗箭頭不會發生碰撞而會持續飛行。

請計算足夠長的時間後,在 W×H 方格中有多少方格會有苦無飛過。

Input Format

第一行輸入兩個用空白隔開的整數 W 和 H,代表方陣的大小。
第二行輸入一個整數 N,代表忍者的數量。
接下來的 N 行中的第 i 行 ($1\leq i\leq N$) 有三個用空白隔開的整數$X_i, Y_i, D_i$,代表忍
者 i 位在第$X_i$行(從左而右)和第$Y_i$列(從上而下)的格子;$D_i$代表忍者$i$面對的方向。
Di = 0 表示忍者 i 面對右方;Di = 1 表示忍者 i 面對上方;Di = 2 表示忍者 i 面對左方;Di = 3 表示忍者 i 面對下方。

對於所有測資,$1\leq N\leq 10^ 5; 1\leq W,H\leq 10^ 9; 1\leq X_i\leq W; 1\leq Y_i\leq H$。
$N,W,H\leq 1000$的測試資料佔分 10%。
$N\leq 1000$的測試資料佔分 40%。

Output Format

輸出在 W×H 方陣中經過足夠的時間後,苦無飛行過的格子數量。

Sample Input

#Sample Input 1
5 4
5
3 3 2
3 2 0
4 2 2
5 4 1
1 1 3

#Sample Input 2
7 6
12
3 2 3
6 3 2
7 1 3
1 5 0
3 6 1
6 6 1
4 5 2
1 3 0
6 5 2
5 1 2
6 4 3
4 1 3

Sample Output

#Sample Output 1
11

#Sample Output 2
29

Hints

Problem Source

APIO 2012
Set by Yihda Yol

Subtasks

No. Testdata Range Score
1 0~2 10
2 0~9 30
3 0~23 60

Testdata and Limits

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