abhatter's blog

help: how to solve CSES Traffic lights?
By abhatter, history, 4 years ago, In English

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-8

Each 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

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Process the queries reversely.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please provide an example?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Removing a light merges two segments into one.

      Adding 2 to 0-2 2-3 3-6 results in 0-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.

      → Reply