提出 #70626669

---

ソースコード 拡げる

import sys
from sortedcontainers import SortedList

input = sys.stdin.readline

N = int(input())
X = list(map(int, input().split()))

sl = SortedList()
d = [0] * (N + 1)
total_sum = 0
INF = 10**18
answers = []

X0 = 0
sl.add((X0, 0))

X1 = X[0]
d[0] = X1 - X0
d[1] = X1 - X0

total_sum = d[0] + d[1]
sl.add((X1, 1))
answers.append(str(total_sum))

for r in range(2, N + 1):
    Xr = X[r - 1]

    idx_s = sl.bisect_left((Xr, r))
    idx_p = idx_s - 1

    (Xp, p) = sl[idx_p]

    if idx_s < len(sl):
        (Xs, s) = sl[idx_s]
    else:
        (Xs, s) = (INF, -1)
        
    new_dr = min(Xr - Xp, Xs - Xr)
    d[r] = new_dr
    total_sum += new_dr
    
    old_dp = d[p]
    
    if idx_p > 0:
        Xpp = sl[idx_p - 1][0]
    else:
        Xpp = -INF
    
    new_dp = min(Xp - Xpp, Xr - Xp)
    d[p] = new_dp
    total_sum = total_sum - old_dp + new_dp
    
    if s != -1:
        old_ds = d[s]

        idx_ss = idx_s + 1
        if idx_ss < len(sl):
            Xss = sl[idx_ss][0]
        else:
            Xss = INF
        
        new_ds = min(Xs - Xr, Xss - Xs)
        d[s] = new_ds
        total_sum = total_sum - old_ds + new_ds

    sl.add((Xr, r))
    
    answers.append(str(total_sum))

print("\n".join(answers))

提出情報

ジャッジ結果