I am trying to solve https://mirror.codeforces.com/contest/86/problem/D where I am using MO's traversal but I am keep getting TLE. Can someone please review my code and help me with slowness? I tried following things so far:
- Changed the way we read input. Reading entire line and converting them to int in memory
- Changed from
Array
toArrayList
since I heardArrays.sort()
hasO(n^2)
in some cases.
I am not sure if there is a flaw in logic or some library methods which is slowing down and giving TLE.
Submission: https://mirror.codeforces.com/contest/86/submission/109548850
You didn't do Mo's completely correctly, the queries should be sorted by the left block and then by the right endpoint.