← 返回题目列表

AtCoder · abc182_e

E. 明里

中文机器翻译题面 查看原题

分数: 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

在这种情况下,所有没有方块的方块都会被照亮。