Задача №115135. Опрос на уроке
На урок истории к Зинаиде Викторовне пришли \(n\) учеников. На дом было задано \(m\) тем, но у учеников было мало времени для подготовки, поэтому \(i\)-й ученик выучил только темы с \(l_i\) по \(r_i\) включительно.
В начале урока каждый ученик держит свою руку на уровне \(0\). Учительница хочет спросить какие-то темы. Происходит это так:
- Учительница спрашивает тему \(k\).
- Если ученик выучил тему \(k\), то он поднимает руку на \(1\), а иначе опускает на \(1\).
Найдите, какая максимальная разность между самой высокой и самой низкой рукой может быть после опроса.
Обратите внимание, рука ученика может опускаться ниже \(0\) .
В первой строке содержатся два целых числа \(n\) и \(m\) (\(2 \le n \le 200\,000, 1 \le m \le 10^9\)) — количество учеников и количество тем соответственно.
В каждой из следующих \(n\) строк содержатся по два целых числа \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le m\)), обозначающих границы отрезка тем, которые выучил \(i\)-й ученик.
Выведите одно число — максимальную разность между самой высокой и самой низкой рукой, которая может быть в классе после опроса.
В первом примере Зинаида Викторовна может спросить темы \(6, 7, 8\). Тогда рука \(2\)-го ученика будет на высоте \(3\), а \(4\)-го — на высоте \(-3\), то есть разность будет равна \(6\).
Во втором примере можно спросить про темы \(1\) и \(3\).
В данной задаче 20 тестов, помимо тестов из условия, каждый из них оценивается в 5 баллов. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие в случае \(n \le 10\), наберут не менее \(10\) баллов.
Решения, корректно работающие в случае \(n \le 100, m \le 100\), наберут не менее \(30\) баллов. Решения, корректно работающие в случае \(n \le 1000\), наберут не менее \(50\) баллов.
4 8 2 6 4 8 2 7 1 5
6
3 3 1 3 2 3 2 2
4