Codeforces 100971.H

Ссылка на задачу

• Codeforces #100971.H — Тусовка у Павла

Комментарии

Заведём массив goingToParty[], в котором будем отмечать, собирается ли прийти на вечеринку каждый из друзей.

Каждая пара (a_i, b_i) даёт 2 события: когда на вечеринку идут a_i человек, i-й друг также приходит (goingToParty[i] = 1), а когда на вечеринку идут (b_i + 1) человек, i-й друг уже не приходит (goingToParty[i] = 0).

Будем перебирать количество друзей k, приходящих на вечеринку (от 1 до n). Для фиксированного количества друзей сначала обработаем все события, связанные с количеством k, а затем требуется вывести длину минимального префикса массива goToParty[], сумма на котором равна k.

Для быстрого подсчёта суммы на префиксе есть два способа:

• Можно использовать дерево Фенвика или дерево отрезков с запросом суммы на отрезке и подбирать минимальный нужный префикс бинарным поиском. Сложность O(log^2(n)).
• Можно использовать спуск по дереву отрезков на сумму, ища индекс k-й единицы. Сложность O(logn).