n1myFurry21

31.10.2020 15:15

Информатика

Есть ответ 👍

Покраска забора Время: 1000ms, Память: 128MB, Сложность: 15% В одной далекой стране жил был Виталик-Гитарист, да к тому же и народный певец да на дуде игрец. Его мама постоянно заставляла делать дела по дому, и на этот раз она попросила его покрасить забор. Забор состоит из прямоугольных панелей одинаковой длины и единичной ширины.

Виталик знает, что мама решила сэкономить на краске и купила самую дешевую, методом экспериментов он смог определить что если нанести краску не менее чем A слоев и не более чем B слоев, забор будет выглядеть как раз нормально. Виталя был достаточно хитер и решил свалить всю работу на младшего брата, который согласился с этим делом.

Для простоты брат решил красить забор секциями, нанося на панели забора текущей секции краску в один слой. Завершив покраску секции он произвольно выбирал другую секцию (и не факт, что эта секция не совпадала полностью или частично с уже покрашенной частью забора) и приступал к ее покраске. Таким образом некоторые панели забора он мог покрасить несколько раз, в то время как другие - ни разу.

Пока брат красил забор Виталик ушел играть на гитаре и петь свои любимые песни, а когда вернулся, он был повергнут в шок! Местами забор был покрыт очень большим слоев краски, а местами и вовсе не покрашен.

К счастью его брат обладал хорошей памятью и помнил какие секции и в каком порядке он красил. Теперь Виталик должен понять сколько панелей забора он не должен переделывать. Чтобы дефекты покраски были менее заметно, брат обязательно покрасил первую и последнюю панели забора.
Входные данные:

Во входном потоке в первой строке записано натуральное число N (N <= 106) - количество закрашенных секций. Во второй строке - натуральные числа A и B (A, B <= 100) - допустимое количество слоев краски. Далее идет список координат N секций в порядке их окрашивания (номер первой Xi и последней Xj панели забора, составляющее текущую секцию). Значения номеров панелей (координат) не превышают 1000.

Пример входного файла (input.txt):

4
1 1
1 2
3 4
5 8
3 6

Выходные данные:

Вывести единственное число - количество панелей которые не придется перекрашивать Виталику-гитаристу.

Пример выходного файла (output.txt):

4