86D - Powerful array . I am trying to solve this problem, but I am getting TLE 50. Can anybody help me. My solution 12479619
UPD: Got AC
→ Обратите внимание
До соревнования
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 14:34:16 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
cnt can be simple array, not map. It will delete O(log(n)) from complexity
I updated my code, but I am getting Tle 50.
I got it accepted 12479877 by changing %lld to %I64d(as Codeforces recomends) and changing comporator a bit.
P.S Sometimes adding some constants to sqrt(n) can make your solution work faster.
Thank you
"Sometimes adding some constants to sqrt(n) can make your solution work faster".. this statement works for me to get accepted :-)
replace function with function object (i.e. struct with overloaded operator()) or with lambda — this also leads to significant speedup
Thanks, but why?
because compiler typically cannot inline function passed by pointer. In many cases sorting with function pointer is 2x-3x times slower than sorting with lambda
Do you have a source on that? I think you may be confusing things with qsort (which may be slower than sort, but that's because it's not templated, not because of function pointer).
Effective C++, 3rd Ed., item 30. And I didn't tested qsort, only std::sort with different comparators. I even tried to compare assembler outputs here — https://goo.gl/5D4vXz. IMO all results are evident
I optimized my code to be able to use it with cout and cin, here is my code 52278174