Задача №115255. Покупка подарков
У маленького Саши есть две подруги, которых он хочет порадовать подарками на Восьмое марта. Для этого он отправился в самый большой торговый центр в городе.
В торговом центре есть \(n\) отделов, в каждом из которых находятся ровно два магазина. Для удобства пронумеруем отделы целыми числами от \(1\) до \(n\). Известно, что подарки в первом магазине \(i\)-го отдела стоят \(a_i\) рублей, а во втором магазине \(i\)-го отдела — \(b_i\) рублей.
Войдя в торговый центр, Саша посетит каждый из \(n\) отделов торгового центра, причем в каждом отделе он зайдет ровно в один магазин. Таким образом, когда Саша попадет в \(i\)-й отдел, он выполнит ровно одно из двух действий:
- Купить подарок первой подруге, потратив на это \(a_i\) рублей.
- Купить подарок второй подруге, потратив на это \(b_i\) рублей.
Для каждой подруги Саша собирается купить хотя бы один подарок. Более того, он хочет подобрать подарки таким образом, чтобы разность цен самых дорогих подарков, купленных подругам, была как можно меньше, чтобы никто не обиделся.
Более формально: пусть \(m_1\) — максимальная цена подарка, купленного первой подруге, а \(m_2\) — максимальная цена подарка, купленного второй подруге. Саша хочет выбрать подарки таким образом, чтобы минимизировать величину \(\lvert m_1 - m_2 \rvert\).
Первая строка содержит одно целое число \(n\) (\(2 \le n \le 500\,000\)) — количество отделов в торговом центре.
Каждая из следующих \(n\) строк содержит два целых числа \(a_i\) и \(b_i\) (\(0 \le a_i, b_i \le 10^9\)) — цены подарков в первом и втором магазине \(i\)-го отдела, соответственно.
Выведите одно целое число — минимальную разность цен самых дорогих подарков, купленных подругам.
В первом примере у Саши есть два возможных варианта действий: купить подарок первой подруге в первом отделе, а второй подруге — во втором отделе, или наоборот. В первом случае \(m_1 = m_2 = 1\), а во втором случае — \(m_1 = m_2 = 2\). В обоих случаях ответ равен \(0\).
Во втором примере можно купить подарки для первой подруги в \(2\)-м, \(4\)-м и \(5\)-м отделах, а для второй подруги — в \(1\)-м и \(3\)-м отделах. Таким образом, \(m_1 = \max(2, 4, 2) = 4\), \(m_2 = \max(5, 3) = 5\). Ответ равен \(\lvert 4 - 5 \rvert = 1\).
Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(a_i\) и \(b_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 16 | \(n \le 20\) | – | 0 | – |
| 2 | 17 | \(n \le 500\) | – | 0, 1 | – |
| 3 | 22 | \(n \le 5000\) | – | 0, 1, 2 | – |
| 4 | 12 | – | \(a_i = b_i\) | – | – |
| 5 | 33 | – | – | 0 – 4 | – |
2 1 2 2 1
0
5 1 5 2 7 3 3 4 10 2 5
1