Painting the Barn

题目描述

农夫约翰不擅长同时处理多项任务。他经常分心，使得很难完成长期项目。现在，他正试图给谷仓的一面刷漆，但他总是先刷一小块矩形区域，然后又被照料奶牛的需求打断，导致谷仓有些部分被刷了比其他部分更多层的油漆。

我们可以将谷仓这一面描述为一个二维的 $x$-$y$ 平面。农夫约翰会刷 $N$ 个矩形，每个矩形的边都与坐标轴平行，并由其左下角与右上角两点的坐标描述。

农夫约翰想给谷仓刷多层漆，以便短期内不需要再次重刷。然而，他也不想浪费时间刷过多的层数。事实证明，刷 $K$ 层漆是最优的。请你帮助他确定：当他刷完所有矩形之后，谷仓上恰好被覆盖了 $K$ 层油漆的面积是多少。

输入格式

第一行输入包含 $N$ 和 $K$（$1 \leq K \leq N \leq 10^5$）。 接下来的 $N$ 行每行包含四个整数 $x_1, y_1, x_2, y_2$，描述一个被刷漆的矩形区域，其左下角为 $(x_1, y_1)$，右上角为 $(x_2, y_2)$。 所有 $x$ 和 $y$ 的取值范围为 $0 \ldots 1000$，且所有矩形的面积均为正。

输出格式

请输出谷仓上恰好被覆盖了 $K$ 层油漆的面积。

3 2
1 1 5 5
4 4 7 6
3 3 8 7

8

提示

题目来源：Nick Wu

标签: USACO|2019|Silver

来源

USACO|2019|Silver