Why the second code executes within 500ms whereas the first one gives TLE(2000ms) ?
1497E1 - Square-Free Division (easy version)
const int N = 1e7 + 5;
vector<int> maping(N);
int i,j;
Code 1
Code 2
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 8 | ecnerwala | 3494 |
| 9 | Um_nik | 3396 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | -is-this-fft- | 161 |
| 3 | maomao90 | 159 |
| 4 | atcoder_official | 158 |
| 4 | cry | 158 |
| 4 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | Dominater069 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 04.10.2024 12:30:48 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Overflow?
int i, j;when i is around N, j is around N*N in the second implementation. So sometimes it gets negative and you do many iterations.You avoid overflow in the first implementation because j*j increases by 2*j+1 each iteration so j*j doesn't go over N + O(sqrt(N))
I am using macro #define int long long so overflow should not be there
Please format your blogs properly & don't forget to mention such important details next time. You should put some effort into describing your problem if you want to get help.
Well, the first code is O(N*sqrt(N)) because j goes from 1 to sqrt(i).
Second code is O(sum n/i^2) we know that O(sum n/i) = O(nlog(n)) therefore your second code is way faster asymptotically.