分数: 500 点
问题陈述
我们有一个网格 H 行和 W 列。让正方形 (i, j) 是位于 i第行和 j该网格中的第列。
有 N 灯泡和 M 块在此网格上。的 i第一个灯泡位于正方形 (A_i, B_i),以及 i第一个块位于正方形 (C_i, D_i)。每个方格最多有一个物体——一个灯泡或一个方块。
每个灯泡都会向四个方向发射光束 - 上、下、左、右 - 一直延伸到带有方块的方块,照亮途中的方块。带灯泡的正方形也被认为是被照亮的。
在没有方块的方格中,找出被灯泡照亮的方格数。
约束
- 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
在没有方块的方块中,以下八个被照亮:
- 广场 (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
在这种情况下,所有没有方块的方块都会被照亮。