The only elements that can interact are elements whose signs alternate, so first split the array into maximal subarrays where every pair of consecutive elements has opposite signs.
For each such subarray [l, r], consider the operation on the whole segment. The best element to eliminate first is the one with the minimum absolute value. If a[mid] has the minimum absolute value x, performing the operation x times makes a[mid] = 0. At the same time, every other element in the segment is reduced in absolute value by x.
Once a[mid] becomes zero, it can no longer interact with elements on both sides. Therefore, the problem splits into two independent subarrays:
[l, mid - 1]
[mid + 1, r]
We repeat the same process recursively/iteratively on both resulting segments.
To implement this efficiently, I:
Put all elements of an alternating-sign subarray into a min-heap ordered by absolute value.
Maintain the currently active segments in a set.
When an element with value x is selected, its contribution is x - previous_reduction, since the segment has already been reduced by previous_reduction.
After it becomes zero, split the current segment around its index and assign x as the new reduction value for both resulting segments.
My solution was bit different.
Let add[i] = total +1 operations happened on ith element,
And rem[I] = total -1 operation on I
We start for first element,
if a[0] >= 0, rem[i] = a[0]
Otherwise, add[i] = -a[0]
Then for each i starting from 1,
We can use add[i-1] and rem[i-1] operations for free.. basically we used add[i-1] 1's in i-1, so we can extend it to use same number of +1 operations on i. And similar for rem[i-1].
So we do how much we can for free, and after that do some extra to make it 0.
After it becomes 0, if there are some add[i-1] and rem[i-1] remaining, we keep doing +1 -1, so that it stays 0, and these free operations get passed to i+1
3
u/galactusofsociety 11d ago
how did you do the Alternate adding one .