Задача E. Дорога и облака.
Задачу добавил: alef
Успешно сдано решений: 24
Жаркое лето привело к возникновению пожаров в лесах. В воздух поднимались гарь и пепел, а не слишком сильный ветер уносил эти облака в сторону дороги. Часть гари из каждого облака осаживалась на дороге.
На тушение пожаров, конечно, нужны средства. И надо убедить Большого Начальника их выделить. Чтобы он проникся мыслью, что нужно выделить достаточно средств, ему необходимо показать, насколько плохо обстоят дела.
Большого Начальника повезут по этой дороге. Лесничие хотели бы знать, какие участки дороги наиболее загрязнены, чтобы сделать остановку на каком-нибудь из них.
Лесничие сообщили Вам координаты облаков гари. Ветер дует строго перпендикулярно дороге. Дорога являет собой прямую линию. Каждое облако (которое можно считать отрезком прямой) при прохождении через дорогу увеличивает толщину слоя гари на одну единицу в каждой точке на покрываемом им участке. Считайте, что облако проходит через дорогу мгновенно.
Ваша задача — по заданным координатам облаков определить, какие участки окажутся наиболее загрязненными после прохождения всех облаков.
Формат входного файла input.txt
Первая строка — целое число N (1 <= N <=10^5), количество облаков, зафиксированных лесничими
Каждая из следующих N строк содержит по два целых числа Lj и Rj через пробел — левую и правую границу очередного облака (1 <= j <= N, –10^9 <= Lj < Rj <= 10^9). Гарантируется, что входной файл не превосходит 4 Мб.
Формат выходного файла output.txt
Первая строка — два целых числа A и S — максимальная толщина слоя гари и количество отрезков, на которых лежит слой гари максимальной толщины.
Каждая из следующих S строк содержит по два целых числа — начало и конец очередного наиболее загрязненного отрезка. Отрезки должны быть перечислены в порядке возрастания координат.
Решения, работающие для N <= 200 и – 10^4 <= Lj < Rj <= 10^4 оцениваются из 25 баллов
Пример входного файла — 1
11
9 15
-4 0
1 4
14 18
-1 2
5 11
-5 3
14 17
8 13
12 18
7 10
Пример выходного файла — 1
4 2
9 10
14 15
Пример входного файла — 2
3
9 15
6 10
10 12
Пример выходного файла — 2
3 1
10 10