← 返回比赛
已结束 GESP排位赛#8
← 上一题 下一题 →

A3031 | 普尔亚的委托

来源官方 / 2024
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

时间限制：1000ms

内存限制：128MB


天地异变，海拉鲁大陆上出现了 $K$ 座古代遗迹，每座古代遗迹呈宽度为 $1$ 的条状，横向或纵向分布在海拉鲁大陆上。

海拉鲁大陆为一个 $N \times M$ 的矩形。

海拉鲁王国的直属研究员「普尔亚」使用古代希卡族的科技造物 ——「希卡石」获取到了 $K$ 座古代遗迹的左上角坐标 $(A_i, B_i)$ 和右下角坐标 $(C_i, D_i)$，委托你根据希卡石上的遗迹坐标，调查出现的古代遗迹将海拉鲁大陆分成了几个部分？

$\large{数据范围}$

- $3 \le N,\ M \le 10^9$
- $1 \le K \le 500$
- $1 \le A_i \le C_i \le N$
- $1 \le B_i \le D_i \le M$
- 对于每一个古代遗迹的坐标存在 $A_i = C_i$（横向分布）或 $B_i = D_i$（纵向分布）。
- 古代遗迹之间可能会有重合的部分。

输入格式

每个测试文件格式如下：

$\tt{N\ M\ K}$

$\tt{A_1\ B_1\ C_1\ D_1}$
$\tt{A_2\ B_2\ C_2\ D_2}$
$\tt{\vdots}$
$\tt{A_K\ B_K\ C_K\ D_K}$

输出格式

对于每个测试文件，输出遗迹将海拉鲁大陆分成了几个部分，若古代遗迹将海拉鲁大陆全部覆盖则输出 $0$。

输入输出样例

输入 #1
10 10 6
1 4 9 4
2 1 2 7
1 9 4 9
5 6 5 10
7 3 7 10
7 7 10 7
输出 #1
5
输入 #2
872591290 272051335 5
1 165504757 872591290 165504757
1 8498686 350676141 8498686
831138698 131078138 831138698 272051335
714614174 186332739 836760236 186332739
790028722 206158653 846122298 206158653
输出 #2
3
C++ 编辑器
输入
输出