Codeforces 100971.H
Перейти к навигации
Перейти к поиску
Ссылка на задачу
Комментарии
Заведём массив goingToParty[], в котором будем отмечать, собирается ли прийти на вечеринку каждый из друзей.
Каждая пара (ai, bi) даёт 2 события: когда на вечеринку идут ai человек, i-й друг также приходит (goingToParty[i] = 1), а когда на вечеринку идут (bi + 1) человек, i-й друг уже не приходит (goingToParty[i] = 0).
Будем перебирать количество друзей k, приходящих на вечеринку (от 1 до n). Для фиксированного количества друзей сначала обработаем все события, связанные с количеством k, а затем требуется вывести длину минимального префикса массива goToParty[], сумма на котором равна k.
Для быстрого подсчёта суммы на префиксе можно использовать дерево Фенвика или дерево отрезков. Подобрать минимальный нужный префикс можно бинарным поиском.