Editorial for LCC '21 Contest 1 J4 - Explosive Candygrams
Submitting an official solution before solving the problem yourself is a bannable offence.
For a candygram ~l~ and ~r~, we know that the number of candygrams in between is ~|r-l|-1~. Therefore, for each candygram, we can loop through all other candygrams. If the number of candygrams between the two is more than or equal to ~R_i~, then we know that the current candygram can be hit. We then take the maximum ~R_i~ of all candygrams we can hit. If we cannot hit any candygrams, then we instead take ~-1~
Consider the above image, where we are calculating the answer for the sixth candygram, the one with the second "2" in its cell. Orange cells denote candygrams which the candygram cannot hit (they are all either the current candygram, have 0 candygrams in between, or 1 candygram in between). The important thing to note is that we "split" the current array into 3 sections, where we must consider all candygrams in the yellow section.
For the current candygram ~i~, all candygrams with index ~j~, such that ~j\le i-R_i-1~ can be hit, as they have at least ~R_i~ candygrams in between. Similarly, all candygrams with index ~j~, such that ~j\ge i+R_i+1~ can be hit, as they have at least ~R_i~ candygrams in between.
We can use a prefix maximum array to quickly calculate the maximum explosiveness on the left side, and a suffix maximum array to quickly calculate the maximum explosiveness on the right side. Let us call the prefix maximum array ~maxTo~ and the suffix maximum array ~maxFrom~
Then, the annoyance of the current candygram is ~\max(maxTo[i - R_i-1], maxFrom[i+R_i+1])~, making sure to account for when we go out of bounds (i.e, ~i-R_i-1~ is before the first element, or ~i+R_i+1~ is past the final element). Furthermore, if we cannot hit any candygram, then the annoyance is ~-1~