On problem 1519C - Berland Regional my submission 125877791 passes test 3 which across all subtests has an n of 200000 in 500ms. On the other hand test 4 has 1 subtest with the same total n of 200000 and that time limits. Why is this?
# | User | Rating |
---|---|---|
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 |
# | User | Contrib. |
---|---|---|
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 | djm03178 | 152 |
On problem 1519C - Berland Regional my submission 125877791 passes test 3 which across all subtests has an n of 200000 in 500ms. On the other hand test 4 has 1 subtest with the same total n of 200000 and that time limits. Why is this?
Name |
---|
If you have numbers $$$a, b \in \mathbb{N}$$$ then $$$a^2 + b^2 \le (a+b)^2$$$ so if you have 1000 test cases where each test case has $$$n \approx 500$$$ and if your algorithm runs in $$$O(n^2)$$$ then it will give you $$$\approx 1000 * 500^2 \approx 1.39 * 10^8$$$ operations which shouldn't, but technically might fit into TL. While if you have 1 test case with $$$n = 2*10^5$$$ then your algorithm will do $$$\approx 4*10^{10}$$$ operations which is way too much.
This segment of your code:
seems to have a time complexity of $$$O(N^2)$$$. In order for the code to pass, you need to optimize it to $$$O(N \log N)$$$ at least.
Edit: Actually the segment above is fine, I misunderstood the code and turns out sum of all
a.size()
is at most $$$n$$$. However this code has $$$O(N^2)$$$ complexity:You need to optimize this part.