G2. Light Bulbs (Hard Version) [Help Required]

Правка en3, от Misa-Misa, 2023-12-20 08:43:04

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.

oth array

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

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. Sombody help me with time complexity.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский Misa-Misa 2023-12-20 08:45:16 0 (published)
en4 Английский Misa-Misa 2023-12-20 08:45:01 170 (saved to drafts)
en3 Английский Misa-Misa 2023-12-20 08:43:04 43 Tiny change: 'rks!<br>\n[sub' -> 'rks!<br>\nLogic lies inside the solve function.<br>\n[sub'
en2 Английский Misa-Misa 2023-12-20 08:41:08 1 (published)
en1 Английский Misa-Misa 2023-12-20 08:40:32 963 Initial revision (saved to drafts)