P83454

Terytoria

难度 6 级 扫描线
讨论 统计 2通过 8提交 25%通过率 旧版界面
时间限制 4 秒 内存限制 256 MB

题目描述

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

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

输入

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

接下来 n 行,每行四个整数 x_1,y_1,x_2,y_2(0\le x_1,x_2 < X,0\le y_1,y_2 < Y,x_1\ne x_2,y_1\ne 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

提示

对于 100\% 的数据,1\le n\le 5\times 10^5,2\le X,Y\le 10^9。

来源

PA

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交