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 solve RMQ with L=1 fixed for max array.
- Finally itterate through all queries and solve (one $$$O(1)$$$ call to the sparse table per query.)
Implementation: https://cses.fi/paste/cec69737a6649398283c56/
My main thought is to use an offline query method instead, but nothing here seems like it should exceed the 1 second time limit.
Ok I solved this, for anyone interested it was an implementation difference. I downloaded one of the large test cases and commented out my code to find it was the preprocessing that was too slow! I made the change from inserting one at a time into a set (~500ms) to putting everything into a vector, sorting it, and then loading a new vector with unique elements (~200ms). The other big change was switching from
map(~600ms) tounordered_map(~100ms!). The rest of the code was all comfortably less than 500ms.Revised implementation: https://cses.fi/paste/9e806894689f8489283d05/
you don't require any pre processing or sparse table stuffs I believe. Sort every range on the basis of start point.
for finding if [l,r] contains any other range find the minimum ending point with starting point >=l, this can be done by maintaining suffix min on ending points and binary search in $$$O(log(n))$$$. If that min ending is <=r then you can print 1 otherwise 0.
for finding if [l,r] is contained in any other range find the max ending point for all starting point<=l, this can be done by maintaining prefix max on ending point and binary search in $$$O(log(n))$$$. if that max ending point>=r, you print 1 else 0.