[USACO19FEB] Painting The Barn S
题目描述
农夫约翰不擅长多任务处理。他经常分心,很难完成长的项目。目前,他正试图在谷仓的一侧上漆,但他一直在画小矩形区域,然后由于照料奶牛的需要而偏离了方向,使得谷仓的某些部分上漆的涂料比其他部分多。
我们可以将谷仓的一侧描述为一个二维 $x-y$ 平面,农夫约翰在该平面上绘制 $n$ 个矩形,每个矩形的边都与坐标轴平行,每个矩形由谷仓的左下角和右上角点的坐标描述。
农夫约翰想在谷仓上涂几层油漆,这样在不久的将来就不需要再重新粉刷了。但是,他不想浪费时间涂太多的油漆。结果表明,$K$ 涂层是最佳用量。请在他画完所有的长方形后,帮他确定谷仓有多少面积被 $K$ 层油漆覆盖。
输入输出格式
输入格式
输入的第一行包含 $n$ 和 $K$。
其余 $n$ 行中的每一行包含四个整数 $x1$、$y1$、$x2$、$y2$,描述正在绘制的矩形区域,左下角 $(x1,y1)$ 和右上角 $(x2,y2)$。所有 $x$ 和 $y$ 值都在 $0$ 到 $1000$ 范围内,并且所有矩形都有正面积。
输出格式
请输出谷仓被 $K$ 层油漆覆盖的区域。
输入输出样例
输入样例 #1
3 2
1 1 5 5
4 4 7 6
3 3 8 7
输出样例 #1
8
说明
$1\le K\le n\le 10^5$。
USACO 2019 二月月赛银牌组第二题。