#P3220. 「PA 2019」Terytoria

「PA 2019」Terytoria

题目描述

题目译自 PA 2019 Runda 3 Terytoria

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

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

输入格式

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

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

输出格式

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

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

数据范围与提示

$ 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 $