B - Snuke's Coloring 2 (ABC Edit) Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

xy 平面上に、左下の座標が (0, 0)、右上の座標が (W, H) で、各辺が x 軸か y 軸に平行な長方形があります。最初、長方形の内部は白く塗られています。

すぬけ君はこの長方形の中に N 個の点を打ちました。i 個目 (1 ≦ i ≦ N) 点の座標は (x_i, y_i) でした。

また、すぬけ君は長さ N の数列 a を決めて、各 1 ≦ i ≦ N に対し、

  • a_i = 1 のときは長方形の x < x_i をみたす領域
  • a_i = 2 のときは長方形の x > x_i をみたす領域
  • a_i = 3 のときは長方形の y < y_i をみたす領域
  • a_i = 4 のときは長方形の y > y_i をみたす領域

を黒く塗りました。

塗りつぶしが終わったあとの長方形内での白い部分の面積を求めてください。

制約

  • 1 ≦ W, H ≦ 100
  • 1 ≦ N ≦ 100
  • 0 ≦ x_i ≦ W (1 ≦ i ≦ N)
  • 0 ≦ y_i ≦ H (1 ≦ i ≦ N)
  • W, H (21:32 追記), x_i, y_i は整数である
  • a_i (1 ≦ i ≦ N) は 1, 2, 3, 4 のいずれかである

入力

入力は以下の形式で標準入力から与えられる。

W H N
x_1 y_1 a_1
x_2 y_2 a_2
:
x_N y_N a_N

出力

塗りつぶしが終わったあとの長方形内での白い部分の面積を出力せよ。

入力例 1

5 4 2
2 1 1
3 3 4

出力例 1

9

すぬけ君が塗りつぶしを始める前の長方形は以下の図のようになっています。

e19e673abcd0882783f635cce9d2f94d.png

(x_1, y_1) = (2, 1)、a_1 = 1 なので、まずすぬけ君は x 座標が 2 より小さい領域を塗りつぶし、長方形は以下のようになります。

f25cd04bbac23c4e5426d70511a9762f.png

(x_2, y_2) = (3, 3)、a_2 = 4 なので、次にすぬけ君は y 座標が 3 より大きい領域を塗りつぶし、長方形は最終的に以下のようになります。

46b0c06fd9eee4f148e1f441f7abca53.png

この最終的な状態における白い部分の面積は 9 なので、出力は 9 となります。

入力例 2

5 4 3
2 1 1
3 3 4
1 4 2

出力例 2

0

塗りつぶした結果、白い部分が残らないこともありえます。

入力例 3

10 10 5
1 6 1
4 1 3
6 9 4
9 4 2
3 1 3

出力例 3

64

Score : 200 points

Problem Statement

There is a rectangle in the xy-plane, with its lower left corner at (0, 0) and its upper right corner at (W, H). Each of its sides is parallel to the x-axis or y-axis. Initially, the whole region within the rectangle is painted white.

Snuke plotted N points into the rectangle. The coordinate of the i-th (1 ≦ i ≦ N) point was (x_i, y_i).

Then, he created an integer sequence a of length N, and for each 1 ≦ i ≦ N, he painted some region within the rectangle black, as follows:

  • If a_i = 1, he painted the region satisfying x < x_i within the rectangle.
  • If a_i = 2, he painted the region satisfying x > x_i within the rectangle.
  • If a_i = 3, he painted the region satisfying y < y_i within the rectangle.
  • If a_i = 4, he painted the region satisfying y > y_i within the rectangle.

Find the area of the white region within the rectangle after he finished painting.

Constraints

  • 1 ≦ W, H ≦ 100
  • 1 ≦ N ≦ 100
  • 0 ≦ x_i ≦ W (1 ≦ i ≦ N)
  • 0 ≦ y_i ≦ H (1 ≦ i ≦ N)
  • W, H (21:32, added), x_i and y_i are integers.
  • a_i (1 ≦ i ≦ N) is 1, 2, 3 or 4.

Input

The input is given from Standard Input in the following format:

W H N
x_1 y_1 a_1
x_2 y_2 a_2
:
x_N y_N a_N

Output

Print the area of the white region within the rectangle after Snuke finished painting.

Sample Input 1

5 4 2
2 1 1
3 3 4

Sample Output 1

9

The figure below shows the rectangle before Snuke starts painting.

e19e673abcd0882783f635cce9d2f94d.png

First, as (x_1, y_1) = (2, 1) and a_1 = 1, he paints the region satisfying x < 2 within the rectangle:

f25cd04bbac23c4e5426d70511a9762f.png

Then, as (x_2, y_2) = (3, 3) and a_2 = 4, he paints the region satisfying y > 3 within the rectangle:

46b0c06fd9eee4f148e1f441f7abca53.png

Now, the area of the white region within the rectangle is 9.

Sample Input 2

5 4 3
2 1 1
3 3 4
1 4 2

Sample Output 2

0

It is possible that the whole region within the rectangle is painted black.

Sample Input 3

10 10 5
1 6 1
4 1 3
6 9 4
9 4 2
3 1 3

Sample Output 3

64