E - Akari Editorial /

Time Limit: 2.5 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

H 行 W 列のマス目があります。このマス目の i 行目 j 列目のマスをマス (i, j) と呼ぶことにします。
このマス目の上には N 個の電球と M 個のブロックが置かれていて、i 個目の電球はマス (A_i, B_i) に、i 個目のブロックはマス (C_i, D_i) に置かれています。一つのマスにある電球とブロックは合計で高々一つです。
全ての電球は、ブロックが置かれているマスに到達するまで届く光を上下左右の 4 方向に放ちます。電球が置かれているマス自身にも光が届くものとします。
マス目上のブロックの置かれていないマスのうち電球の光が届くものの数を求めてください。

制約

  • 1 \le H, W \le 1500
  • 1 \le N \le 5 \times 10^5
  • 1 \le M \le 10^5
  • 1 \le A_i \le H
  • 1 \le B_i \le W
  • 1 \le C_i \le H
  • 1 \le D_i \le W
  • (A_i, B_i) \neq (A_j, B_j)\ \ (i \neq j)
  • (C_i, D_i) \neq (C_j, D_j)\ \ (i \neq j)
  • (A_i, B_i) \neq (C_j, D_j)
  • 入力はすべて整数

入力

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

H W N M
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_N B_N
C_1 D_1
C_2 D_2
C_3 D_3
\hspace{15pt} \vdots
C_M D_M

出力

マス目上のブロックの置かれていないマスのうち、電球の光が届くものの数を出力せよ。

入力例 1

3 3 2 1
1 1
2 3
2 2

出力例 1

7

ブロックの置かれていないマスのうち、マス (3, 2) を除いた全てのブロックに光が届きます。

入力例 2

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

出力例 2

8

ブロックの置かれていないマスのうち、電球の光が届くものは以下の 8 個です。

  • マス (1, 1)
  • マス (1, 2)
  • マス (1, 3)
  • マス (1, 4)
  • マス (2, 2)
  • マス (3, 3)
  • マス (3, 4)
  • マス (4, 4)

入力例 3

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

出力例 3

24

この場合、ブロックが置かれていないマスには全て光が届きます。

Score : 500 points

Problem Statement

We have a grid with H rows and W columns. Let square (i, j) be the square at the i-th row and j-th column in this grid.
There are N bulbs and M blocks on this grid. The i-th bulb is at square (A_i, B_i), and the i-th block is at square (C_i, D_i). There is at most one object - a bulb or a block - at each square.
Every bulb emits beams of light in four directions - up, down, left, and right - that extend until reaching a square with a block, illuminating the squares on the way. A square with a bulb is also considered to be illuminated. Among the squares without a block, find the number of squares illuminated by the bulbs.

Constraints

  • 1 \le H, W \le 1500
  • 1 \le N \le 5 \times 10^5
  • 1 \le M \le 10^5
  • 1 \le A_i \le H
  • 1 \le B_i \le W
  • 1 \le C_i \le H
  • 1 \le D_i \le W
  • (A_i, B_i) \neq (A_j, B_j)\ \ (i \neq j)
  • (C_i, D_i) \neq (C_j, D_j)\ \ (i \neq j)
  • (A_i, B_i) \neq (C_j, D_j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W N M
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_N B_N
C_1 D_1
C_2 D_2
C_3 D_3
\hspace{15pt} \vdots
C_M D_M

Output

Print the number of squares illuminated by the bulbs among the squares without a block.

Sample Input 1

3 3 2 1
1 1
2 3
2 2

Sample Output 1

7

Among the squares without a block, all but square (3, 2) are illuminated.

Sample Input 2

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

Sample Output 2

8

Among the squares without a block, the following eight are illuminated:

  • Square (1, 1)
  • Square (1, 2)
  • Square (1, 3)
  • Square (1, 4)
  • Square (2, 2)
  • Square (3, 3)
  • Square (3, 4)
  • Square (4, 4)

Sample Input 3

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

Sample Output 3

24

In this case, all the squares without a block are illuminated.