AtCoder Regular Contest 070 - NarrowRectangles

AtCoDeer the deer found N rectangle lying on the table, each with height 1.
If we consider the surface of the desk as a two-dimensional plane, the i-th rectangle i(1≤i≤N) covers the vertical range of [i-1,i] and the horizontal range of [l_i,r_i], as shown in the following figure:

AtCoDeer will move these rectangles horizontally so that all the rectangles are connected.
For each rectangle, the cost to move it horizontally by a distance of x, is x.
Find the minimum cost to achieve connectivity.
It can be proved that this value is always an integer under the constraints of the problem.

-----Constraints-----
 - All input values are integers.
 - 1≤N≤10^5
 - 1≤l_i<r_i≤10^9

-----Partial Score-----
 - 300 points will be awarded for passing the test set satisfying 1≤N≤400 and 1≤l_i<r_i≤400.

-----Input-----
The input is given from Standard Input in the following format:
N
l_1 r_1
l_2 r_2
:
l_N r_N

-----Output-----
Print the minimum cost to achieve connectivity.

-----Sample Input-----
3
1 3
5 7
1 3

-----Sample Output-----
2

The second rectangle should be moved to the left by a distance of 2.

Source: atcoder | Difficulty: VERY_HARD


Solutions:
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]
INF = 10 ** 18
from heapq import heappush, heappop
(l0, r0) = P[0]
L = [-l0 + 1]
R = [l0 - 1]
s = t = 0
res = 0
for i in range(N - 1):
	(l0, r0) = P[i]
	(l1, r1) = P[i + 1]
	s += r1 - l1
	t += r0 - l0
	if -s - L[0] <= l1 - 1 <= t + R[0]:
		heappush(L, -l1 + 1 - s)
		heappush(R, l1 - 1 - t)
	elif l1 - 1 < -s - L[0]:
		heappush(L, -l1 + 1 - s)
		heappush(L, -l1 + 1 - s)
		p = -heappop(L) - s
		heappush(R, p - t)
		res += p - (l1 - 1)
	elif t + R[0] < l1 - 1:
		heappush(R, l1 - 1 - t)
		heappush(R, l1 - 1 - t)
		p = heappop(R) + t
		heappush(L, -p - s)
		res += l1 - 1 - p
print(res)


N = int(input())
P = [list(map(int, input().split())) for i in range(N)]
INF = 10 ** 18
from heapq import heappush, heappop
(l0, r0) = P[0]
L = [-l0 + 1]
R = [l0 - 1]
s = t = 0

def debug(L, s, t, R):
	L0 = L[:]
	Q1 = []
	Q2 = []
	while L0:
		Q1.append(-s - heappop(L0))
	R0 = R[:]
	while R0:
		Q2.append(t + heappop(R0))
	print(('debug:', *Q1[::-1] + Q2))
res = 0
for i in range(N - 1):
	(l0, r0) = P[i]
	(l1, r1) = P[i + 1]
	s += r1 - l1
	t += r0 - l0
	if -s - L[0] <= l1 - 1 <= t + R[0]:
		heappush(L, -l1 + 1 - s)
		heappush(R, l1 - 1 - t)
	elif l1 - 1 < -s - L[0]:
		heappush(L, -l1 + 1 - s)
		heappush(L, -l1 + 1 - s)
		p = -heappop(L) - s
		heappush(R, p - t)
		res += p - (l1 - 1)
	elif t + R[0] < l1 - 1:
		heappush(R, l1 - 1 - t)
		heappush(R, l1 - 1 - t)
		p = heappop(R) + t
		heappush(L, -p - s)
		res += l1 - 1 - p
print(res)


import sys
input = sys.stdin.readline
from heapq import heappop, heappush
N = int(input())
LR = [[int(x) for x in input().split()] for _ in range(N)]
(L, R) = LR[0]
S_lower = [-L]
S_upper = [L]
min_f = 0
add_lower = 0
add_upper = 0
prev_w = R - L
push_L = lambda x: heappush(S_lower, -x)
push_R = lambda x: heappush(S_upper, x)
pop_L = lambda : -heappop(S_lower)
pop_R = lambda : heappop(S_upper)
for (L, R) in LR[1:]:
	w = R - L
	add_lower -= w
	add_upper += prev_w
	x = pop_L() + add_lower
	y = pop_R() + add_upper
	(a, b, c, d) = sorted([x, y, L, L])
	push_L(a - add_lower)
	push_L(b - add_lower)
	push_R(c - add_upper)
	push_R(d - add_upper)
	min_f += c - b
	prev_w = w
print(min_f)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappush, heappushpop
N = int(readline())
m = map(int, read().split())
(L, R) = zip(*zip(m, m))
A = [-L[0]]
B = [L[0]]
addA = 0
addB = 0
min_f = 0
for n in range(1, N):
	p = R[n - 1] - L[n - 1]
	q = R[n] - L[n]
	addA += -q
	addB += p
	a = -A[0] + addA
	b = B[0] + addB
	x = L[n]
	if x <= a:
		min_f += a - x
		heappush(A, -x + addA)
		y = -heappushpop(A, -x + addA) + addA
		heappush(B, y - addB)
	elif x >= b:
		min_f += x - b
		heappush(B, x - addB)
		y = heappushpop(B, x - addB) + addB
		heappush(A, -y + addA)
	else:
		heappush(A, -x + addA)
		heappush(B, x - addB)
print(min_f)