Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Misa-Misa's blog

By Misa-Misa, history, 4 months ago, In English

I wanted to ask why my solution for this problem works!
Logic lies inside the solve function.
238096776

Logic

First, I find the intervals which can be just turned on by just 1 bulb, and then for each interval, I find number of bulbs that can single handedly turn on the whole interval.


To do this i consider this bulb and it counterpart bulb (which also lies in this interval), then i query in the range formed by the two bulbs the min value and max value of oth (using segment tree), and then expand my range to the new indices.
If range becomes equal to total interval size then we lit up whole range, else if range size did not increase and whole interval is not covered then we can not cover this whole range so we skip this blub.
I am not sure why this works fast.

oth array

for each bulb i store the index of it counterpart in oth array.

Sombody help me with time complexity.

  • Vote: I like it
  • +1
  • Vote: I do not like it