CDRN04 time-complexity

Hi all,
I was trying this question. here is my solution using mo’s algo. For merging two clubs, I used DSU ( with path compression and weighted union ). I think my solution is O(q*sqrt(n)) (mo’s algorithm dominating the time complexity ). The solution is giving TLE on 3 test cases, which I fail to understand why.

Am I calculating the complexity wrong ?
Is there any way to make my solution pass without changing the logic ?
Please let me know.

@l_returns @aryanc403 ?? @anyone_willing_to_help

Change your sort fn of queries for constant factor optimization. https://codeforces.com/blog/entry/59346?#comment-429584

1 Like

Thanks to those who tried to look into it ( I can see some clicks on the link ) :smiley:. Solved. here is the accepted solution. I see many 20 pts solution there. If anyone faces the same, use array instead of map to count frequency as this adds extra log(n) time.

Wow. That was not known, will look into this. Thanks :innocent::innocent:
P.S. optimisations didn’t work. Log(n) factor is huge for this optimisation I think.