- что я могу сделать чтоб моя программа работала быстрее ?
- задача — 61E - Enemy is weak
- код — 6713532
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.11.2024 20:41:44 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
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 и подобных структур? Я так понимаю, даже если реально, оно уже потеряет своё преимущество в скорости?
молись!