提出 #53129902

---

ソースコード 拡げる

from collections import deque

class SlidingMinimumElement:
    def __init__(self, a):
        self.left = 0
        self.right = 0
        self.a = a
        self.que = deque()

    def min(self, l, r):
        for i in range(self.right, r):
            while self.que and self.a[self.que[-1]] > self.a[i]:
                self.que.pop()
            self.que.append(i)
        while self.que and self.que[0] < l:
            self.que.popleft()
        self.left = l
        self.right = r
        return self.a[self.que[0]]

class SlidingMaximumElement:
    def __init__(self, a):
        self.left = 0
        self.right = 0
        self.a = a
        self.que = deque()

    def max(self, l, r):
        for i in range(self.right, r):
            while self.que and self.a[self.que[-1]] < self.a[i]:
                self.que.pop()
            self.que.append(i)
        while self.que and self.que[0] < l:
            self.que.popleft()
        self.left = l
        self.right = r
        return self.a[self.que[0]]

n, k = map(int, input().split())
p = list(map(int, input().split()))
index_p = [0] * n
for i in range(n):
    index_p[p[i] - 1] = i

sl_min = SlidingMinimumElement(index_p)
sl_max = SlidingMaximumElement(index_p)
ans = float('inf')

for i in range(n - k + 1):
    l = i
    r = i + k
    tmp_min = sl_min.min(l, r)
    tmp_max = sl_max.max(l, r)
    ans = min(ans, tmp_max - tmp_min)


print(ans)

提出情報

ジャッジ結果