Подкиньте, пожалуйста, максимально много хороших задач на Декартово дерево для отработки.
upd: ну, не жадничайте, пожалуйста.
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.11.2024 11:57:38 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
1846 1028 1090 1521 1439 1523
блок на информатиксе — сразу 6 задач.
И парочка задач с кф.
431E - Химический эксперимент
420D - Фокус со стаканчиками
P.S. Буду рад, если кто подкинет ещё задач с тимуса. Желательно, чтобы их нельзя было решить каким-нибудь деревом отрезков или Фенвика, как те, что я кинул :)
Может быть 1316
Фенвиком же решается ну очень просто
Блин, и действительно.
1839
Кстати, было бы любопытно взглянуть на решение 1846 декартовым деревом, укладывающееся в TL.
Вот
Время: 0.39 Память: 5 216 КБ
а чем обусловлен такой способ делать приоритеты? просто в первый раз такое вижу.
Я хотел, чтобы приоритеты были случайные и разные. Вроде это самый простой способ такого добиться, памяти не жалко :)
Забавно. Моё решение с добавлением и удалением через разрезание и склейку получало TL17 (515 мс). Решение с несколько оптимизированными добавлением и удалением, аналогичное вашему, получало TL18 (531 мс). Использовался msvc.
Пошёл на тимус и переотправил первое решение на g++, получил AC (468 мс). Отправил ваше решение под msvc, получил AC (390 мс). Вновь отправил своё первое решение под msvc, получил AC (500 мс).
Вроде бы уже отмечалось, что результаты на тимусе зависят от времени посылки и загруженности системы, но каждый раз этому удивляешься, как впервые. Особенно в задачах с таким жёстким TL.
Эх, никак не могу получить АС с таким кодом.
Пробовал srand(n) и случайную перестановку, как в коде выше, пробовал сдавать под разными компиляторами.
Может быть, кто-нибудь мне подскажет какое-то очевидно (не для меня, естественно) замедляющее место?
В любом случае, спасибо, увидел способ вставки/удаления явно более быстрый, чем разделение и склейка.
После серии экспериментов выяснилось, что не всё так просто:
TL18 (0.515 c, 4824 КБ)
AC (0.343 c, 4824 КБ)
(различие в строке 54)
TL17 (0.515 с, 4824 КБ)
AC (0.5 с, 4824 КБ)
(различия в строках 54, 73, 74)
Так что дело, по-видимому, ещё и в тестах. При разрезании одинаковые ключи существенно важно оставлять в левой части.
Декартово дерево
Дерево отрезков
Переоптимизированная sqrt-декомпозиция
spoj