Let \(f(i,x)\) be the minimum damage received until the \(i\)-th gunshot, and at the moment of that gunshot, Snuke is at coordinate \(x\).

We can transit \(f\) as follows:

\[ f(i,x)=F_i(x)+\min_{x-(t_i-t_{i-1})\le y\le x+(t_i-t_{i-1})} f(i-1,y) \]

where \(F_i(x)\) is a function that calculates the damage received from the \(i\)-th gunshot when Snuke is at \(x\). For example, when \(d_i=1\) and \(x_i=10\), \(F_i(x)=\max(x-10,0)\).

The important thing to notice is that \(F_i\) is always convex. The taking minimum operation does not change the convexity of the function, nor does adding another convex function to it. So, \(f(i)\), if seen as a function for \(x\), is convex.

A trick to solve such problems is to maintain the turning points of \(f\), and keeping the following true:

• when passing through a turning point, the slope increases by \(1\).

With the above and the turning points kept, we can calculate \(f(n,x)\) for any \(x\) easily by scanning the whole function.

We use two heaps to maintain turning points. The first one keeps turning points where the slopes are negative, the second one keeps turning points where the slopes are positive. Also the heap should support adding \(x\) to the whole heap. Keep the value of \(p\) as the minimum value of \(f\).

Let us explain how to maintain the transition using the two heaps.

• make \(f(x)\) the minimum of \(f(x-L)\dots f(x+L)\): note that this is actually inserting a segment with slope \(0\) into \(f\). So we add the first heap by \(-L\) and the second by \(L\).
• add \(f(x)\) by \(F_i(x)\): we only explain the part when \(d_i=0\). Here we should substract \(1\) from the slope of a prefix of \(f\). If the smallest value in the second heap is greater than or equal to \(X_i\), just insert \(X_i\) into the first heap. Otherwise insert it into the second heap and put the smallest value in the second heap into the first heap, and add \(p\) by \(X_i-M\) (\(M\) is the largest value in the first heap now).

This part is quite hard to understand, so I suggest drawing a picture while reading it.

To make sure that we do not go outside the function, we should add \(n\) zeros to both heaps in the beginning.

Time complexity: \(O(n\log n)\).

Similar problems: CF1229F