#3220. 「PA 2019」Terytoria

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 PA 2019 Runda 3 Terytoria

在二维平面直角坐标系上,有一个长度为 X ,宽度为 Y 的地图,注意这个地图的左边界和右边界是连通的,下边界和上边界也是连通的,换言之它是个球形结构。

在这个地图里,有 X \times Y 个格子以及 n 个边平行坐标轴的矩形。你只知道每个矩形两个对顶点的坐标,请问在最好情况下,被所有 n 个矩形都覆盖住的格子数量有多少?

输入格式

第一行三个正整数 n, X, Y

接下来 n 行,每行四个整数 x_1, y_1, x_2, y_2 ,表示第 i 个矩形两个对顶点的坐标为 (x_1, y_1) (x_2, y_2)

输出格式

输出一行一个整数,即被所有 n 个矩形都覆盖住的格子数量的最大可能值。

样例

样例输入 1

2 10 7
2 1 8 6
5 2 4 4

样例输出

15

样例说明

下图列举了一些情况,其中第 3 种情况是最优的。

ter.png

数据范围与提示

1 \le n \le 5\times 10^5, 2 \le X, Y \le 10^9, 0 \le x_1, x_2 < X, 0 \le y_1, y_2 < Y, x_1 \ne x_2, y_1 \ne y_2