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

Revision en5, by Misa-Misa, 2023-12-20 08:45:16

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


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.


  Rev. Lang. By When Δ Comment
en5 English Misa-Misa 2023-12-20 08:45:16 0 (published)
en4 English Misa-Misa 2023-12-20 08:45:01 170 (saved to drafts)
en3 English 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 English Misa-Misa 2023-12-20 08:41:08 1 (published)
en1 English Misa-Misa 2023-12-20 08:40:32 963 Initial revision (saved to drafts)