How can this be made faster?

Revision en2, by EugeneJudo, 2021-08-06 01:13:45

I'm attempting to solve, and I believe I have the right idea, but i'm getting TLE for all large test cases. My algorithm is to:

  1. Transform inputs so that they're constrained to the range [0,400000]
  2. For every interval start, keep track of the smallest and largest interval ending.
  3. Build a sparse table to solve Range Minimum Queries on the minimum array.
  4. Build simpler (cheaper) array to RMQ with L=1 fixed.
  5. Finally itterate through all queries and solve (one $$$O(1)$$$ call to the sparse table per query.)


My main thought is to use an offline query method instead, but nothing here seems like it should exceed the 1 second time limit.


  Rev. Lang. By When Δ Comment
en3 English EugeneJudo 2021-08-06 01:16:01 20
en2 English EugeneJudo 2021-08-06 01:13:45 16 Tiny change: ', but i'm failing all large' -> ', but i'm getting TLE for all large'
en1 English EugeneJudo 2021-08-06 01:13:13 777 Initial revision (published)