Codeforces 100971.H: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://codeforces.com/gym/100971/problem/H Codeforces #100971.H — Остров сокровищ] == Коммент…») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== Ссылка на задачу == | == Ссылка на задачу == | ||
* [http://codeforces.com/gym/100971/problem/H Codeforces #100971.H — | * [http://codeforces.com/gym/100971/problem/H Codeforces #100971.H — Тусовка у Павла] | ||
== Комментарии == | == Комментарии == | ||
Версия от 17:05, 8 июня 2016
Ссылка на задачу
Комментарии
Заведём массив goingToParty[], в котором будем отмечать, собирается ли прийти на вечеринку каждый из друзей.
Каждая пара (ai, bi) даёт 2 события: когда на вечеринку идут ai человек, i-й друг также приходит (goingToParty[i] = 1), а когда на вечеринку идут (bi + 1) человек, i-й друг уже не приходит (goingToParty[i] = 0).
Будем перебирать количество друзей k, приходящих на вечеринку (от 1 до n). Для фиксированного количества друзей сначала обработаем все события, связанные с количеством k, а затем требуется вывести длину минимального префикса массива goToParty[], сумма на котором равна k.
Для быстрого подсчёта суммы на префиксе можно использовать дерево Фенвика или дерево отрезков. Подобрать минимальный нужный префикс можно бинарным поиском.