Submission #8346938

---

Source Code Expand

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter

"""
・各番号の人に対して、手前の番号で最寄りの人を見つければよい
・大きい番号の人から埋めていく。埋まってる部分の連結成分の左右の端を管理
"""

N,M = map(int,readline().split())
C = [N] + list(map(int,read().split()))

INF = 10**15
Csorted = sorted([(0,-INF)] + list(enumerate(C,1)) + [(N+2,INF)], key = itemgetter(1))

c_rank = [0] * (N+3)
for k,(i,c) in enumerate(Csorted):
    c_rank[i] = k

C1 = [x[1] for x in Csorted]

left = list(range(1,N+4))
right = list(range(-1,N+2))
answer = 0
for n in c_rank[2:-1][::-1]:
    # n 番目を埋める
    l = left[n-1]; r = right[n+1]
    left[r] = l; right[l] = r
    x1 = C1[l-1]
    x2 = C1[r+1]
    x = C1[n]
    answer += min(x-x1,x2-x)

print(answer)

Submission Info

Judge Result