Олимпиадный тренинг

Задача . Задание 10


Задача

Темы:
Проспект длиной K метров освещён N фонарями, стоящими вдоль него. Администрация города выяснила, что количество включённых фонарей избыточно для освещения всего проспекта – какие-то из них можно выключить, чтобы сэкономить электроэнергию, при этом проспект все равно останется освещён полностью. Входной файл содержит данные о метках начала и конца отрезков, освещаемых фонарями. Определите, какое максимальное количество фонарей можно выключить так, чтобы проспект остался освещён полностью, а также общее количество фонарей, которые, если их включить, освещают K-й метр проспекта.
Примечание: начало проспекта определено 1-м метром, конец – K-м метром.
Входные данные представлены в файле 26-139.txt следующим образом. В первой строке входного файла находятся два натуральных числа: N (N ≤ 10 000) – количество фонарей, стоящих вдоль проспекта, и K (K ≤ 10 000) – длина проспекта. Следующие N строк содержат пары чисел, обозначающих метку начала и метку конца отрезка проспекта, освещаемого фонарем. Каждое из чисел натуральное, не превосходящее 10 000.
Запишите в ответе два числа: максимальное количество фонарей, которые можно выключить, и количество фонарей, которые, если их включить, освещают K-й метр проспекта.
Пример входного файла:
5 50
1 30
28 50
20 40
1 10
31 50
При таких исходных данных можно выключить 3 фонаря: второй, третий и четвёртый. K-й метр освещается двумя фонарями (если они включены): фонарь {28, 50} и фонарь {15, 50}. Ответ: 3 2.
Файл

 

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя