Problem link: http://www.spoj.com/problems/ADAUNIQ/
My solution: https://ideone.com/srH91b
Verdict: TLE
How do I optimize my solution? Any help is really appreciated.
[Update] Got AC :) I missed out the fact that block sizes are of n^(2/3)
# | User | Rating |
---|---|---|
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 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
8 | Dominater069 | 154 |
8 | nor | 154 |
Problem link: http://www.spoj.com/problems/ADAUNIQ/
My solution: https://ideone.com/srH91b
Verdict: TLE
How do I optimize my solution? Any help is really appreciated.
[Update] Got AC :) I missed out the fact that block sizes are of n^(2/3)
Name |
---|
You're not supposed to compare right ends by buckets, instead, just compare values. So, replace
if(r1 != r2) return r1 < r2;
withif(a.r != b.r) return a.r < b.r;
In order to experiment, I did that too. Still got TLE :(
Ah, I see. The problem is with time updates, these might take up to O(nq) (lines 81, 82)
If you wish to know how to use Mo's algorithm with updates, check out this blog post, but I doubt that it will be fast enough.
Thank You :)
Thanks a ton :) I understood where I was wrong logically. Got AC now :)
Good job! There is also a online solution.
comes from a 2D range query.
Try maintaining the set of segments [u, v] such that au = av and there is no y such that u < y < v and au = ay.
Though you got AC, I'd like to mention one more thing.
I see you wrote —
This might be the reason of your getting TLE. I got 2-3 times too.
Instead of doing this, precompute block numbers and do —
This will significantly reduce your run time.