Подкиньте, пожалуйста, максимально много хороших задач на Декартово дерево для отработки.
upd: ну, не жадничайте, пожалуйста.
Подкиньте, пожалуйста, максимально много хороших задач на Декартово дерево для отработки.
upd: ну, не жадничайте, пожалуйста.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
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