Problem: Snuke has a permutation (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1).  Now, he will perform the following operation **exactly once** :    * Choose K consecutive elements in P and sort them in ascending order.  Find the number of permutations that can be produced as P after the operation.

Submission attempts (in order):
INF = float('inf')

class SegmentTree:
    def __init__(self, size):
        self._size = (1 << size.bit_length())
        self._data = [INF] * (self._size * 2)

    def update(self, index, value):
        index += self._size - 1
        self._data[index] = value
        while index > 0:
            index = (index - 1) // 2
            self._data[index] = min(self._data[index * 2 + 1], self._data[index * 2 + 2])

    def __query(self, qLeft, qRight, node, left, right):
        if right <= qLeft or qRight <= left:
            return INF
        if qLeft <= left and right <= qRight:
            return self._data[node]

        leftVal = self.__query(qLeft, qRight, node * 2 + 1, left, (left + right) // 2)
        rightVal = self.__query(qLeft, qRight, node * 2 + 2, (left + right) // 2, right)
        return min(leftVal, rightVal)

    def query(self, left, right):
        return self.__query(left, right, 0, 0, self._size)

N, K = map(int, input().split())
P = list(map(int, input().split()))

minTree = SegmentTree(N)
maxTree = SegmentTree(N)

for i, p in enumerate(P):
    minTree.update(i, p)
    maxTree.update(i, -p)

ans = 1
hasSame = False
seq = 1
for i in range(1, K):
    if P[i - 1] < P[i]:
        seq += 1
    else:
        seq = 1
if seq >= K:
    hasSame = True

for left in range(N - K):
    right = left + K

    if P[right - 1] < P[right]:
        seq += 1
    else:
        seq = 1

    if minTree.query(left, right) == P[left] and maxTree.query(left + 1, right + 1) == P[right]:
        continue
    else:
        if seq >= K:
            if hasSame:
                continue
            else:
                hasSame = True
        ans += 1

print(ans)

from collections import deque

class SlideMin:
    def __init__(self, leng):
        self.que = deque([])
        self.leng = leng

    def top(self):
        return self.que[0]

    def getQue(self):
        return self.que

    def update(self, index, value=0):
        while self.que:
            if self.que[-1][1] >= value:
                self.que.pop()
            else:
                break

        self.que.append((index, value))

        if self.que[0][0] == index - self.leng:
            self.que.popleft()

N, K = map(int, input().split())
P = list(map(int, input().split()))

maxQ = SlideMin(K)
minQ = SlideMin(K)

for i in range(K):
    maxQ.update(i, -P[i])
    minQ.update(i, P[i])

ans = 1
hasSame = False
seq = 1
for i in range(1, K):
    if P[i - 1] < P[i]:
        seq += 1
    else:
        seq = 1
if seq >= K:
    hasSame = True

for left in range(N - K):
    right = left + K

    if P[right - 1] < P[right]:
        seq += 1
    else:
        seq = 1

    maxQ.update(right, -P[right])

    if left == minQ.top()[0] and right == maxQ.top()[0]:
        pass
    else:
        if seq < K:
            ans += 1
        else:
            if not hasSame:
                hasSame = True
                ans += 1

    minQ.update(right, P[right])

print(ans)

Verdicts: Wrong Answer

Accepted