On problem 1519C - Берляндский отбор 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 | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
3 | cry | 159 |
5 | atcoder_official | 158 |
5 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | maroonrk | 151 |
10 | Dominater069 | 150 |
On problem 1519C - Берляндский отбор 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.