Расскажите, plz, как решаются задачи E и G
UPD. Спасибо за содержательные ответы.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.11.2024 08:32:02 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Пусть bi - кол-во чисел из a, которые не меньше i (1 ≤ i ≤ n). Для того, чтобы перестановка существовала, должно выполняться: bn ≥ 1, bn - 1 ≥ 2, ... bi ≥ n + 1 - i, ... b1 ≥ n. Для проверки этого я хранил в дереве отрезков для минимума числа bi - (n + 1 - i). Теперь, если в данный момент минимум на всём массиве меньше 0, то ответ NIE, иначе ответ TAK. Когда приходит запрос изменения числа x на y, если x < y, то надо прибавить 1 ко всем числам отрезка [x + 1, y], если x > y, то надо отнять 1 от всех чисел отрезка [y + 1, x].
Но мне почему-то кажется, что существует решение проще.
Е:
Решаем в оффлайне. Строим все дерево из работников. Для каждого уровня нужно упорядочить работников. Можно просто запустить DFS для каждого работника запоминаем время входа и выхода. И упорядочивасть согласно времени входа. Время выхода тоже понадобится :)
Для каждого уровня строится свое дерево отрезков, которые умеет считать сумму на отрезке.
Далее идем по запросам и обрабатываем их. Если добавление работника, то в дерево отрезков для данного уровня увеличиваем значение соответствующее данному работнику.
Если нужно посчитать кол-во работников на некотором уровне ниже от работника i. То мы знаем что эти работники в дереве находятся на некотором уровне h. Для этого уровня h у нас есть дерево отрезков и в нем как раз нужно посчитать сумму. Но нужно не общее кол-во добавленных, а только в поддерево, т.е. на самом деле только те работники, у которых время входа больше, чем время входа работника i, и в то же время меньше времени выхода работника i. Т.е. можно для каждого уровня хранить времена входов всех работников, и там двумя бинарными поисками, найти отрезок для которого нам надо посчитать сумму в дерево отрезков :)
Надеюсь более или менее понятно :)
Интересно как решается задача I есть какие-нибудь идеи ?
A* ?
требуется их разбить на три множества A, B, C
так чтобы S(A) <= S(B) <= S(C) и S(C) - S(A) минимально.
вывести S(C) - S(A). S(x) - сумма элементов в множестве.