← 返回题目列表

AtCoder · awc0007_d

D. 重叠广告区域的调查

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

分数: 400 分

问题陈述

高桥和青木分别计划在 N \times N 网格公告板。公告板的每个单元格都用坐标表示 (r, c) (1 \leq r \leq N, 1 \leq c \leq N),其中 r 是从顶部开始计数的行号, c 是从左侧算起的列号。

高桥计划发布 A 矩形广告,青木计划张贴 B 布告栏上的矩形广告。每个广告覆盖由其左上角单元格指定的矩形区域 (r_1, c_1) 和右下单元格 (r_2, c_2)。也就是说,所有细胞 (r, c) 满意 r_1 \leq r \leq r_2 和 c_1 \leq c \leq c_2 已被覆盖。

公告板管理员担心高桥和青木的广告覆盖的单元格看起来不美观,因此想提前知道此类重叠单元格的总数。

找出至少一个高桥广告和至少一个青木广告覆盖的单元格数量。即使同一个小区被多种广告组合覆盖,也只算一次。

约束

  • 1 \leq N \leq 500
  • 1 \leq A \leq 100
  • 1 \leq B \leq 100
  • 对于高桥的每个广告 i (1 \leq i \leq A): 1 \leq r_{1,i} \leq r_{2,i} \leq N, 1 \leq c_{1,i} \leq c_{2,i} \leq N
  • 对于青木的每个广告 j (1 \leq j \leq B): 1 \leq r_{1,j} \leq r_{2,j} \leq N, 1 \leq c_{1,j} \leq c_{2,j} \leq N
  • 所有输入值均为整数

输入

N A B
r_{1,1} c_{1,1} r_{2,1} c_{2,1}
r_{1,2} c_{1,2} r_{2,2} c_{2,2}
:
r_{1,A} c_{1,A} r_{2,A} c_{2,A}
r'_{1,1} c'_{1,1} r'_{2,1} c'_{2,1}
r'_{1,2} c'_{1,2} r'_{2,2} c'_{2,2}
:
r'_{1,B} c'_{1,B} r'_{2,B} c'_{2,B}
  • 第一行包含电路板尺寸 N,高桥的广告数量 A,以及青木的广告数量 B,用空格分隔。
  • 以下 A 行每行描述高桥的一则广告。
  • 的 i-第广告(1 \leq i \leq A) 给出为四个空格分隔的整数,表示左上角的单元格 (r_{1,i}, c_{1,i}) 和右下角的单元格 (r_{2,i}, c_{2,i}).
  • 以下 B 行每行描述 Aoki 的一则广告。
  • 的 j-第广告(1 \leq j \leq B) 给出为四个空格分隔的整数,表示左上角的单元格 (r'_{1,j}, c'_{1,j}) 和右下角的单元格 (r'_{2,j}, c'_{2,j}).

输出

在一行上输出高桥的广告和青木的广告重叠的单元格数。


示例输入 1

5 1 1
1 1 3 3
2 2 4 4

示例输出 1

4

示例输入 2

10 2 2
1 1 5 5
3 7 6 10
4 3 8 6
2 8 5 10

示例输出 2

15

示例输入 3

100 3 2
1 1 50 50
40 60 80 100
70 1 100 40
30 30 60 70
80 10 100 50

示例输出 3

1323