I'm attempting to solve https://cses.fi/problemset/task/2168, and I believe I have the right idea, but i'm getting TLE for all large test cases. My algorithm is to:
- Transform inputs so that they're constrained to the range [0,400000]
- For every interval start, keep track of the smallest and largest interval ending.
- Build a sparse table to solve Range Minimum Queries on the minimum array.
- Build simpler (cheaper) array to RMQ with L=1 fixed.
- 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.