Məsələlər
Покраска сарая (серебро)
Покраска сарая (серебро)
Фермер Джон не умеет выполнять несколько задач одновременно. Он часто отвлекается, что затрудняет выполнение длинных проектов. В настоящее время он пытается покрасить одну сторону своего коровника, но продолжает рисовать небольшие прямоугольные области, а затем отвлекается из-за необходимости заботиться о своих коровах, оставляя некоторые части коровника окрашенными большим количеством слоев краски, чем другие.
Сторону сарая можно описать как 2D $x \times y$ плоскость, на которой фермер Джон рисует $n$ прямоугольников со сторонами, параллельными осям координат, каждый из которых описывается координатами его нижнего левого и верхнего правого угла.
Фермер Джон хочет нанести несколько слоев краски на сарай, чтобы его не нужно было перекрашивать в ближайшем будущем. Однако он не хочет тратить время на нанесение чрезмерного количества слоев краски. Оказывается, $k$ слоев краски - оптимальное количество. Помогите ему определить, какая площадь сарая покрыта ровно $k$ слоями краски после того, как он закрасит все свои прямоугольники.
\InputFile
Первая строка содержит числа $n$ и $k~(1 \le k \le n \le 10^5)$. Каждая из оставшихся $n$ строк содержит четыре целых числа $x_1, y_1, x_2, y_2$, описывая окрашиваемую прямоугольную область с нижним левым углом $(x_1, y_1)$ и верхним правым углом $(x_2, y_2)$. Все значения $x$ и $y$ находятся в диапазоне $0 ... 1000$, и все прямоугольники имеют положительную площадь.
\OutputFile
Выведите площадь сарая, покрытую ровно $k$ слоями краски.
Giriş verilənləri #1
3 2 1 1 5 5 4 4 7 6 3 3 8 7
Çıxış verilənləri #1
8