- что я могу сделать чтоб моя программа работала быстрее ?
- задача — 61E - Enemy is weak
- код — 6713532
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3976 |
| 2 | tourist | 3815 |
| 3 | jqdai0815 | 3682 |
| 4 | ksun48 | 3614 |
| 5 | orzdevinwang | 3526 |
| 6 | ecnerwala | 3514 |
| 7 | Benq | 3482 |
| 8 | hos.lyric | 3382 |
| 9 | gamegame | 3374 |
| 10 | heuristica | 3357 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | -is-this-fft- | 165 |
| 3 | Um_nik | 161 |
| 3 | atcoder_official | 161 |
| 5 | djm03178 | 157 |
| 6 | Dominater069 | 156 |
| 7 | adamant | 154 |
| 8 | luogu_official | 152 |
| 9 | awoo | 151 |
| 10 | TheScrasse | 147 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2025 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.01.2025 14:43:40 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
Since N is <=1000000 you can make the numbers smaller in range [1...N] and then make your end=N.
Example:
Before
4
10 8 3 1
After
4
4 3 2 1
О, количество 3-инверсий. Прикольно.
Если кому интересно, вот задача для более общего случая 1523
P.S. Буду признателен, если кто-то пояснит, почему моё решение ловит RTE 21
UPD: Забудьте :) Я уже просто забыл как оно работает и не понимал, что обращаюсь к числам в позиции до 1е9.
You can easily solve it by using that formula!!
I realy dont know it brother. If i udrestand it i will help to you :-D
Сожми координаты.
Поменять map на unordered_map и выбрать компилятор со стандартом C++0x.
What is the difference between map and unordered_map ?
They do the same thing, but differ in performance. For
in both the average and the worst case. For
std::map, search/insert/remove isstd::unordered_map, search/insert/remove is O(1) on average, but O(n) in the worst case. Also, as it follows from the name, instd::unordered_mapthe elements are not ordered in any particular order.std::mapis typically implemented as a balanced binary tree, andstd::unordered_mapis implemented as a hashtable.Thanks!
Очень странно, что два дерева фенвика не заходят ( Я думал, что они будут самыми быстрыми ). Можно попробовать переписать ваше решение через два дерева отрезков (правда скорее всего нерекурсивное, рекурсия не зайдет). А можно через два декартовых дерева по явному ключу 6714050 но тогда нужно очень оптимально их использовать, а то не зайдёт 6713978.
Вполне нормально они заходят, если координаты сжать.
Я имел ввиду сжатые координаты без map. У него вообще что-то странное. Он сжимает map'om, что не очень эффективно. Мне кажется, что лучше чем-нибудь посортить копию массива за O(n*log(n)) по возрастанию. Потом числу b[i] ( это копия массива а отсортированная ) будет соответствовать число i. Потом идем по массиву а и дихой по массиву b вычисляем позицию pos числа a[i] в массиве b. И делаем a[i]=pos. Вот сжатие готово. А массив, а не нарушился с точки зрения условия задачи.
Ну, я об этом и говорил.
Кстати, может тут есть знатоки — реально сделать дерево Фенвика по несжатым координатам на O(QlogC) памяти и O(logC) на запрос без unordered_map и подобных структур? Я так понимаю, даже если реально, оно уже потеряет своё преимущество в скорости?
молись!