Codeforces 100971.H

Материал из Олимпиадное программирование в УлГТУ
Версия от 20:12, 8 июня 2016; Ctrlalt (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

Комментарии

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

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

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

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

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