Codeforces 100971.H: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «== Ссылка на задачу == * [http://codeforces.com/gym/100971/problem/H Codeforces #100971.H — Остров сокровищ] == Коммент…»)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
== Ссылка на задачу ==
== Ссылка на задачу ==
* [http://codeforces.com/gym/100971/problem/H Codeforces #100971.H — Остров сокровищ]
* [http://codeforces.com/gym/100971/problem/H Codeforces #100971.H — Тусовка у Павла]


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


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


[[Category: Сборник задач: Codeforces]]
[[Category: Сборник задач: Codeforces]]

Текущая версия от 20:12, 8 июня 2016

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

Комментарии

Заведём массив 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).