CF1710B Rain

You are the owner of a harvesting field which can be modeled as an infinite line, whose positions are identified by integers. It will rain for the next $ n $ days. On the $ i $ -th day, the rain will be centered at position $ x_i $ and it will have intensity $ p_i $ . Due to these rains, some rainfall will accumulate; let $ a_j $ be the amount of rainfall accumulated at integer position $ j $ . Initially $ a_j $ is $ 0 $ , and it will increase by $ \max(0,p_i-|x_i-j|) $ after the $ i $ -th day's rain. A flood will hit your field if, at any moment, there is a position $ j $ with accumulated rainfall $ a_j>m $ . You can use a magical spell to erase exactly one day's rain, i.e., setting $ p_i=0 $ . For each $ i $ from $ 1 $ to $ n $ , check whether in case of erasing the $ i $ -th day's rain there is no flood.

N/A

N/A

In the first test case, if we do not use the spell, the accumulated rainfall distribution will be like this: If we erase the third day's rain, the flood is avoided and the accumulated rainfall distribution looks like this: In the second test case, since initially the flood will not happen, we can erase any day's rain. In the third test case, there is no way to avoid the flood.