Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### Tobby_And_Friends's blog

By Tobby_And_Friends, history, 14 months ago, ,

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)

•
• +8
•

 » 14 months ago, # |   0 You're not supposed to compare right ends by buckets, instead, just compare values. So, replace if(r1 != r2) return r1 < r2; with if(a.r != b.r) return a.r < b.r;
•  » » 14 months ago, # ^ |   0 In order to experiment, I did that too. Still got TLE :(
•  » » » 14 months ago, # ^ |   -8 Ah, I see. The problem is with time updates, these might take up to O(nq) (lines 81, 82)
•  » » » » 14 months ago, # ^ |   0 The time limit given is 8s. I read about MO's algorithm with updates in a blog (https://rezwanarefin01.github.io/posts/block-decomposition-01) and I got to know that the time complexity of the query is O(n ^(5/3)) which is around 7 seconds for this problem. Besides, the judge's solution is off-line as well. Is there any way to cleverly implement that part?
 » 14 months ago, # |   0 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.
•  » » 14 months ago, # ^ |   +8 Thank You :)
•  » » 14 months ago, # ^ |   +8 Thanks a ton :) I understood where I was wrong logically. Got AC now :)
•  » » » 14 months ago, # ^ |   0 Good job! There is also a online solution. Hint comes from a 2D range query. Another hintTry maintaining the set of segments [u, v] such that au = av and there is no y such that u < y < v and au = ay.
 » 14 months ago, # |   0 Though you got AC, I'd like to mention one more thing.I see you wrote — int l1 = a.l/SZ, l2 = b.l/SZ; int r1 = a.r/SZ, r2 = b.r/SZ; This might be the reason of your getting TLE. I got 2-3 times too.Instead of doing this, precompute block numbers and do — int l1 = blc[a.l], l2 = blc[b.l]; ...... This will significantly reduce your run time.
 » 14 months ago, # |   0 Can it be solved using offline BIT in something like O(nlg2(n)) just like the one without updates (DQUERY)?