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):
import numpy as np
(n,k),p = [list(map(int, s.split())) for s in open(0)]
p = np.array(p)

p_isordered = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
if p_isordered[:k-1].all():
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    for j in range(k-1):
        if not p_isordered[i+j+1]:
            break
    else:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

import numpy as np
import sys
input = sys.stdin.readline
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
p = np.array(p)

p_isorder = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
for j in range(k-1):
    if not p_isorder[j]:
        break
else:
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if (q.argmin()==0 and q.argmax()==k):
        ans -= 1
        dec = True
    
    for j in range(k-1):
        if not p_isorder[i+j+1]:
            break
    else:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)
print(0)

import numpy as np
(n,k),p = [list(map(int, s.split())) for s in open(0)]
p = np.array(p)

p_isordered = p[1:]>p[:-1]
p_cumsum = p_isordered.cumsum()

ans = n - k + 1
no_change = False
if p_cumsum[k-2]==k-1:
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

%%time
import numpy as np
(n,k),p = [list(map(int, s.split())) for s in open(0)]
p = np.array(p)

p_isordered = p[1:]>p[:-1]
p_cumsum = p_isordered.cumsum()

ans = n - k + 1
no_change = False
if p_isordered[:k-1].all():
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

import numpy as np
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
p = np.array(p)

ans = n - k + 1
no_change = False
for j in range(k-1):
    if p[j] > q[j+1]:
        break
else:
    no_change = True


for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if (q.argmin()==0 and q.argmax()==k):
        ans -= 1
        dec = True
    for j in range(1,k):
        if q[j] > q[j+1]:
            break
    else:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

import numpy as np
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
p = np.array(p)

p_ordered = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
if p_ordered[:k-1].all():
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if (q.argmin()==0 and q.argmax()==k):
        ans -= 1
        dec = True
    
    if p_ordered[i+1:i+k].all():
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)
print(0)

import numpy as np
(n,k),p = [list(map(int, s.split())) for s in open(0)]
p = np.array(p)

p_isorder = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
if p_isorder[:k-1].all():
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if p_isorder[i+1:i+k].all():
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

import numpy as np
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
p = np.array(p)

p_isorder = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
for j in range(k-1):
    if not p_isorder[j]:
        break
else:
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if (q.argmin()==0 and q.argmax()==k):
        ans -= 1
        dec = True
    
    for j in range(k-1):
        if not p_isorder[i+j+1]:
            break
    else:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)
print(0)

import numpy as np
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
p = np.array(p)

p_isorder = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
for j in range(k-1):
    if not p_isorder[i+j]:
        break
else:
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if (q.argmin()==0 and q.argmax()==k):
        ans -= 1
        dec = True
    
    for j in range(k-1):
        if not p_isorder[i+j+1]:
            break
    else:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

import numpy as np
import heapq

(n,k),p = [list(map(int, s.split())) for s in open(0)]

p_np = np.array(p)
p_cumsum = (p_np[1:]>p_np[:-1]).cumsum()

_min = [(x,i) for i,x in enumerate(p[:k])]
_max = [(-x,i) for i,x in enumerate(p[:k])]
heapq.heapify(_min)
heapq.heapify(_max)

ans = n - k + 1
no_change = False
if p_cumsum[k-2]==k-1:
    no_change = True

for i in range(n-k):
    decrease = False
    
    heapq.heappush(_min, (p[i+k], i+k))
    heapq.heappush(_max, (-p[i+k], i+k))
    
    while _min[0][1] < i:
        heapq.heappop(_min)
    while _max[0][1] < i:
        heapq.heappop(_max)
    
    if (_min[0][0]==p[i] and -_max[0][0]==p[i+k]):
        ans -= 1
        decrease = True
    
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not decrease:
            ans -= 1
        no_change = True

print(ans)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Accepted