Problem link: https://cses.fi/problemset/task/1163
Hello, I am using an interval tree to solve this problem but for 2 test-cases my solution are timing out. I have provided a drawing for the sample input given in the problem description.
0-8
/ \
/ \
/ \
0-3 3-8
/ \ / \
/ \ / \
0-2 2-3 3-6 6-8Each time, I am adding a new interval I am returning the max diff of intervals to the root node and returning it as an answer
Could you please help me
Process the queries reversely.
can you please provide an example?
Removing a light merges two segments into one.
Adding 2 to
0-2 2-3 3-6results in0-3 3-6. Just store the split points.As a note, processing the queries in order also works, but you need an extra ordered data structure (such as a priority queue) to maintain the segments.