АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1651. Закраска прямой - 2

Ограничение времени: 1 сек.
Ограничение памяти:262144 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

Определение. Интервал прямой с целочисленными координатами [a, b) содержит левую границу – точку a и не содержит правую границу – точку b.

Интервал от 0 до 109 выкрасили в белый цвет. Затем было выполнено N операций перекрашивания. При каждой операции цвета в интервале, границы которого задаются, меняются на противоположный (белый на черный, черный на белый).

Требуется написать программу, которая найдет самый длинный интервал белого цвета после заданной последовательности операций перекрашивания.

Исходные данные

Входные данные содержат в первой строке число N (1 <= N <= 500000) и затем N строк с границами интервалов (числа в диапазоне от 0 до 109).

Результат

Выведите одно число – длину самого большого белого интервала.

Пример

Исходные данныеРезультат
4
20 50
10 35
40 90
100 1000000000
15

Статистика Послать на проверку Обсуждение задачи Автор/источник: acmp.ru/index.asp?main=task&id_task=467 (ограничения увеличены )
Задачи по темам / Сортировка и поиск /
985. Двоичный поиск в упорядоченном массиве 1651. 1649. Инверсии-2 293. Построение пирамиды
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.