pribic's blog

[Help] MO's algoridhm getting TLE — Java
By pribic, history, 4 years ago, In English

I am trying to solve https://codeforces.net/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:

  1. Changed the way we read input. Reading entire line and converting them to int in memory
  2. Changed from Array to ArrayList since I heard Arrays.sort() has O(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://codeforces.net/contest/86/submission/109548850

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

You didn't do Mo's completely correctly, the queries should be sorted by the left block and then by the right endpoint.

→ Reply