Akari

题目描述

我们有一个 $H$ 行 $W$ 列的格子。记格子 $(i, j)$ 为该网格中第 $i$ 行第 $j$ 列的格子。
该网格上有 $N$ 个灯泡和 $M$ 个障碍物。第 $i$ 个灯泡位于格子 $(A_i, B_i)$，第 $i$ 个障碍物位于格子 $(C_i, D_i)$。每个格子至多有一个物体——灯泡或障碍物。
每个灯泡向四个方向发射光线——上、下、左、右——光线会一直延伸直到遇到有障碍物的格子，沿途照亮经过的格子。有灯泡的格子也视为被照亮。 在没有障碍物的格子中，求被灯泡照亮的格子数量。

输入格式

输入从标准输入按以下格式给出： $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$

输出格式

在没有障碍物的格子中，输出被灯泡照亮的格子数量。

3 3 2 1
1 1
2 3
2 2

7

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

8

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

24

提示

$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)$ 输入中的所有数值均为整数。在没有障碍物的格子中，除了格子 $(3, 2)$ 之外的格子都被照亮。
在没有障碍物的格子中，以下八个被照亮：

格子 $(1, 1)$ 格子 $(1, 2)$ 格子 $(1, 3)$ 格子 $(1, 4)$ 格子 $(2, 2)$ 格子 $(3, 3)$ 格子 $(3, 4)$ 格子 $(4, 4)$
在这种情况下，所有没有障碍物的格子都被照亮。

标签: AtCoder|abc182E

来源

AtCoder|abc182E