- Описание
- Отправленные решения
264. Цветные прямоугольники
Задача быстрой отрисовки окон на экране может быть очень нетривиальной. С другой стороны, если ни одного пикселя окна приложения сейчас не видно пользователю, то можно сэкономить время на обработке некоторых событий в приложении.
На экране нарисованы $n$ прямоугольников со сторонами параллельными сторонам экрана (известен порядок от самого нижнего прямоугольника к самому верхнему). Для удобства будем считать, что каждый прямоугольник имеет свой уникальный цвет: $i$-му прямоугольнику соответствует цвет $i$.
В задаче будем рассматривать экран фиксированного разрешения: пиксели имеют координаты $[0..1279] \times [0..1919]$.
Необходимо посчитать, сколько различных цветов сейчас видно на экране. Другими словами, нужно найти количество прямоугольников, не полностью покрытых последующими прямоугольниками в последовательности.
Формат ввода
Первая строка содержит единственное число $n$ — количество прямоугольников ($1 \leq n \leq 3000$).
Следующие $n$ строк содержат описания прямоугольников: 4 разделенных пробелом числа $x_1, y_1, x_2, y_2$ — координаты углов прямоугольника ($0 \leq x_1 \leq x_2 \leq 1279, 0 \leq y_1 \leq y_2 \leq 1919$). Все пиксели внутри прямоугольника и на его границе должны быть покрашены в новый цвет.
Прямоугольники перечислены в порядке от самого нижнего (рисуется первым) до самого верхнего (рисуется последним).
Формат вывода
Вывод должен содержать одно число — количество различных цветов, которые видно на экране.
Ограничения
Ограничение времени
10 с
Ограничение памяти
256 МБ
Пример 1
3
0 0 1 1
1 1 2 2
1 1 1 1
3
Пример 2
3
0 0 1 1
1 1 1 1
1 1 2 2
2
Пример 3
5
1 1 2 2
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2
4
Пример 4
5
2 2 2 2
1 1 1 1
1 2 1 2
2 1 2 1
1 1 2 2
1
Пример 5
5
0 0 1000 1000
0 0 500 500
0 502 500 1000
502 0 1000 500
502 502 1000 1000
5
Пример 6
3
0 0 100 100
10 10 90 90
30 20 80 70
3