A New Beginning
Contest: Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)
Difficulty rating: 3300
Tags: data structures, dp, geometry, sortings

Annie has gotten bored of winning every coding contest and farming unlimited rating. Today, she is going to farm potatoes instead.

Annie's garden is an infinite 2D plane. She has $$$n$$$ potatoes to plant, and the $$$i$$$-th potato must be planted at $$$(x_i,y_i)$$$. Starting at the point $$$(0, 0)$$$, Annie begins walking, in one step she can travel one unit right or up (increasing her $$$x$$$ or $$$y$$$ coordinate by $$$1$$$ respectively). At any point $$$(X,Y)$$$ during her walk she can plant some potatoes at arbitrary points using her potato gun, consuming $$$\max(|X-x|,|Y-y|)$$$ units of energy in order to plant a potato at $$$(x,y)$$$. Find the minimum total energy required to plant every potato.

Note that Annie may plant any number of potatoes from any point.

Input format:
The first line contains the integer $$$n$$$ ($$$1 \le n \le 800\,000$$$).

The next $$$n$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i,y_i \le 10^9$$$), representing the location of the $$$i$$$-th potato. It is possible that some potatoes should be planted in the same location.

Output format:
Print the minimum total energy to plant all potatoes.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In example $$$1$$$, Annie can travel to each spot directly and plant a potato with no energy required.

In example $$$2$$$, moving to $$$(1,0)$$$, Annie plants the second potato using $$$1$$$ energy. Next, she travels to $$$(1,1)$$$ and plants the first potato with $$$0$$$ energy.

Example input:
2
1 1
2 2

Example output:
0

Example input:
2
1 1
2 0

Example output:
1

Editorial:
Observe that for any point $$$(x,y)$$$ and some path $$$A$$$, the minimum distance from $$$A$$$ to $$$(x,y)$$$ will occur on the intersection of $$$A$$$ and the antidiagonal of $$$(x,y)$$$. Here the antidiagonal is defined as a line $$$y=-x+c$$$.
Proof:
Assume $$$(a,b)$$$ is the intersection of $$$A$$$ and the antidiagonal of $$$(x,y)$$$. If $$$(a,b) = (x,y)$$$, this distance is obviously minimal as it is equal to 0.
Now consider the case where $$$(a,b) \neq (x,y)$$$. As a result of $$$(a,b)$$$ being on the antidiagonal, two properties will be true:
• $$$|x-a| = |y-b|$$$.
• Either $$$a > x$$$ and $$$b < y$$$ or $$$a < x$$$ and $$$b > y$$$.
When you move forward on the path, increasing $$$b$$$ will only make $$$|y-b|$$$ larger. Thus, no matter how you change $$$a$$$, $$$\max(|x-a|,|y-b|)$$$ will always increase or stay the same.
When you move backward on the path, decreasing $$$a$$$ will only make $$$|x-a|$$$ larger. Thus, no matter how you change $$$b$$$, $$$\max(|x-a|,|y-b|)$$$ will always increase or stay the same.
Thus, the shortest distance will always occur at $$$(a,b)$$$.
Now we rotate the grid $$$45$$$ degrees clockwise so that the antidiagonals are now vertical lines on the new grid. Your movements on the grid now go from $$$(x,y)$$$ to $$$(x+1,y+1)$$$ or $$$(x+1,y-1)$$$. Furthermore, it is now optimal to plant a potato when you are on the same x coordinate as the potato. When you are at $$$(x,a)$$$, planting a potato at $$$(x,b)$$$ costs $$$\frac{|a-b|}{2}$$$.
From here we can observe a slow dp. Define $$$dp[x][y]$$$ as the minimum cost of any path that goes from $$$(0,0)$$$ to $$$(x,y)$$$ and plant all potatoes $$$(a,b)$$$ such that $$$a \leq x$$$. Note: this function is only defined for when $$$x$$$ and $$$y$$$ have the same parity. This is as a point $$$(x,y)$$$ in the old grid translates to $$$(x+y,x-y)$$$ in the new grid and $$$x+y$$$ has the same parity as $$$x-y$$$. For speed, we also only calculate $$$dp[x][y]$$$ when there is a potato with a x-coordinate of $$$x$$$.
The transition is then established as $$$dp[x][y] = (\min{dp[a][b]} \forall y-(x-a) \leq b \leq y+(x-a)) + (\sum{\frac{|y-z|}{2}} \forall potatoes (x,z))$$$, where $$$a$$$ is the last x-coordinate containing a potato.
This runs in $$$\mathcal{O}(n \cdot 10^9)$$$.
This dp can then be optimized using slope trick. If you are not familiar with slope trick, we recommend learning it first at Slope trick explained and [Tutorial] Slope Trick.
Instead of maintaining a $$$2$$$ dimensional array, we can maintain functions $$$f_x$$$ where $$$f_x(y) = dp[x][y]$$$. To transition from $$$f_i$$$ to $$$f_j$$$, we first set $$$f_i(a) = \min{f_i(b)} \forall a-(j-i) \leq b \leq a+(j-i)$$$. This can be done by maintaining the center/minimum of the slope trick function and then offsetting all values in the left priority queue by $$$-(j-i)$$$ and offsetting all values in the right priority queue by $$$j-i$$$.
Finally, we have to add the costs of the potatoes. Each of the potatoes $$$(x,y)$$$ is just a function $$$g$$$ such that $$$g(a) = \frac{|y-a|}{2}$$$. These functions can then be added onto $$$f_i$$$ finishing the conversion to $$$f_j$$$. The final answer is then the minimum of the last function.
Final Complexity: $$$\mathcal{O}(n \log n)$$$.