Problem:


Score : 700 points

Problem Statement

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.

Constraints

2 \leq N \leq 200000

2 \leq K \leq N

0 \leq P_i \leq N-1

P_0,P_1,\cdots,P_{N-1} are all different.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_0 P_1 \cdots P_{N-1}

Output

Print the number of permutations that can be produced as P after the operation.

Sample Input 1

5 3
0 2 1 4 3

Sample Output 1

2

Two permutations can be produced as P after the operation: (0,1,2,4,3) and (0,2,1,3,4).

Sample Input 2

4 4
0 1 2 3

Sample Output 2

1

Sample Input 3

10 4
2 0 1 3 7 5 4 6 8 9

Sample Output 3

6



Sample input:
5 3
0 2 1 4 3


Sample output:
2

Submission status: Time Limit Exceeded

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

out={}
for n,p in enumerate(P):
    changed=None
    if n<=len(P)-K:
        s=sorted(P[n:n+K])
        if n==0:
            changed=s+P[n+K:]
            out["".join(map(str,changed))]=changed 
        elif n==len(P)-K:
            changed=P[0:n]+s
            out["".join(map(str,changed))]=changed 
        else:
            changed=P[:n]+s+P[n+K:]
            out["".join(map(str,changed))]=changed

print(len(out))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
INF = 10**10
MOD = 10**9+7

N, K = map(int, input().split())
P = [int(x) for x in input().split()]
s = set()
for i in range(N-K+1):
    s.add(tuple(P[:i]+sorted(P[i:i+K])+P[i+K:]))
print(len(s))

Submission status: Time Limit Exceeded

Solution code:
import sys
 
n, k = map(int, input().split(' '))
p = [int(num) for num in input().split(' ')]
 
if n == k:
  print('1')
  sys.exit()
 
ope_count = n - k + 1
ans = ope_count
exist_sorted = 0
for i in range(ope_count):
  target = p[i:i+k]
  for j in range(1, k):
    if target[j -1] > target[j]:
      break
  else:
    ans -= 1
    exist_sorted = 1
    continue
  if i != (ope_count -1):
    next_one = p[i+k]
    if target[0] == min(target) and next_one > max(target):
      ans -= 1
 
print(ans + exist_sorted)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

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

p_ordered = np.array([False]*(n-1))
for i in range(n-1):
    if p[i] < p[i+1]:
        p_ordered[i]=True

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)

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        diff = ''
        ans = 0
        for i, v in enumerate(input().split()):
            if int(v) != i:
                diff += '1'
            else:
                diff += '0'
            if i >= K:
                if int(diff[-K:], 2) > 0:
                    ans += 1

        print(max(1, ans))


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

line1 = input().strip()
line2 = input().strip()

N, K = list(map(int, line1.split(' ')))
P = list(map(int, line2.split(' ')))

count = 1

ordered = [0] * N
ordered[0] = 1
for i in range(1, N):
    if P[i - 1] < P[i]:
        ordered[i] = ordered[i - 1] + 1
    else:
        ordered[i] = 1

flg = False

if ordered[K - 1] == K:
    flg = True

sorted_target = []

for i in range(K):
    bisect.insort(sorted_target, P[i])

for i in range(K, N):
    bisect.insort(sorted_target, P[i])

    if ordered[i] >= K:
        if not flg:
            count += 1
        flg = True

    elif P[i] != sorted_target[-1] or P[i - K] != sorted_target[0]:
        count += 1

    sorted_target.pop(bisect.bisect_left(sorted_target, P[i - K]))

print(count)

Submission status: Time Limit Exceeded

Solution code:
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] > p[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)

Submission status: Time Limit Exceeded

Solution code:
import bisect

line1 = input().strip()
line2 = input().strip()

N, K = list(map(int, line1.split(' ')))
P = list(map(int, line2.split(' ')))

count = 1

ordered = [0] * N
ordered[0] = 1
for i in range(1, N):
    if P[i - 1] < P[i]:
        ordered[i] = ordered[i - 1] + 1
    else:
        ordered[i] = 1

flg = False

if ordered[K - 1] == K:
    flg = True

sorted_target = []

for i in range(K):
    bisect.insort(sorted_target, P[i])

for i in range(K, N):
    bisect.insort(sorted_target, P[i])

    if ordered[i] >= K:
        if not flg:
            count += 1
        flg = True

    elif P[i] != sorted_target[-1] or P[i - K] != sorted_target[0]:
        count += 1

    sorted_target.remove(P[i - K])

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,k=map(int,input().split())
p=list(map(int,input().split()))

count=n-k+1
first=0
seq=1

for i in range(k-1):
    if p[i]<=p[i+1]:
        seq+=1
    else:
        seq=1
        
if seq>=k:
    first+=1
    max_p=p[k-1]
    min_p=p[0]
else:
    max_p=np.max(p[0:k])
    min_p=np.min(p[0:k])
    
    
    
for i in range(n-k):
    if p[k+i]>=p[k-1+i]:
        seq+=1
        if seq>=k:
            max_p=p[k+i]
            min_p=p[i+1]
            if first==1:
                count-=1
            else:
                first+=1
        else:
            max_p=max(max_p,p[k+i])
            if p[i]==min_p:
                min_p=np.min(p[i+1:k+i])
                if max_p==p[k+i]:
                    count-=1
            elif p[i]==max_p:
                max_p=np.max(p[i+1:k+i+1])
    else:
        seq=1
        min_p=min(min_p,p[k+i])
        if min_p==p[i]:
            min_p=np.min(p[i+1:k+i+1])
        elif max_p==p[i]:
            max_p=np.max(p[i+1:k+i])

print(count)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    ls = []
    if n == k:
        print(1)
        return 1
    for i in range(n - k + 1):
        s = sorted(p[i:i + k])
        l = p[:i] + s + p[i + k:]
        if l not in ls:
            ls.append(l)
    print(len(ls))


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def main():

    n,k=map(int,input().split())
    x=list(map(int,input().split()))
    
    min_list=[]
    max_list=[]
    m=262143+n
    segtree=[-1]*m
    
    for i in range(262143,m):
        segtree[i]=x[i-262143]
    	
    for i in range(262142,-1,-1):
        if 2*i+1>=m:
            segtree[i]=-1
        elif 2*i+2>=m:
            segtree[i]=segtree[2*i+1]
        else:
            segtree[i]=min(segtree[2*i+1],segtree[2*i+2])
    
    for i in range(n-k+2):
        qq=[[i,i+k-2,0,0]]
        s=set()
        while qq:
            ii,jj,now,l=qq.pop()
            kubun=2**l
            now2=now-kubun+1
            width=262144//kubun
            left=width*now2
            right=width*(now2+1)-1
            if ii<=left and right<=jj:
                s.add(segtree[now])
            elif jj<left or right<ii:
                continue
            else:
                qq.append([ii,jj,2*now+1,l+1])
                qq.append([ii,jj,2*now+2,l+1])
        min_list.append(min(s))
       
    for i in range(262142,-1,-1):
        if 2*i+1>=m:
            segtree[i]=n+1
        elif 2*i+2>=m:
            segtree[i]=segtree[2*i+1]
        else:
            segtree[i]=max(segtree[2*i+1],segtree[2*i+2])
    
    for i in range(n-k+2):
        qq=[[i,i+k-2,0,0]]
        s=set()
        while qq:
            ii,jj,now,l=qq.pop()
            kubun=2**l
            now2=now-kubun+1
            width=262144//kubun
            left=width*now2
            right=width*(now2+1)-1
            if ii<=left and right<=jj:
                s.add(segtree[now])
            elif jj<left or right<ii:
                continue
            else:
                qq.append([ii,jj,2*now+1,l+1])
                qq.append([ii,jj,2*now+2,l+1])
        max_list.append(max(s))
        
    cnt=0
    flag=[True]*(n-k+1)
    first=False
    for i in range(n-1):
        if x[i]<x[i+1]:
            cnt+=1
        else:
            cnt=0
        if cnt>=k-1:
            if first==False:
                first=True
            else:
                flag[i-k+2]=False
    
    for i in range(1,n-k+1):
        if x[i-1]<min_list[i] and max_list[i]<x[i+k-1]:
            flag[i]=False
            
    print(sum(flag))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    n,k=map(int,input().split())
    x=list(map(int,input().split()))
    
    min_list=[]
    max_list=[]
    m=262143+n
    segtree=[-1]*m
    
    for i in range(262143,m):
        segtree[i]=x[i-262143]
    	
    for i in range(262142,-1,-1):
        if 2*i+1>=m:
            segtree[i]=-1
        elif 2*i+2>=m:
            segtree[i]=segtree[2*i+1]
        else:
            segtree[i]=min(segtree[2*i+1],segtree[2*i+2])
    
    for i in range(n-k+2):
        qq=[[i,i+k-2,0,0]]
        s=set()
        while qq:
            ii,jj,now,l=qq.pop()
            kubun=2**l
            now2=now-kubun+1
            width=262144//kubun
            left=width*now2
            right=width*(now2+1)-1
            if ii<=left and right<=jj:
                s.add(segtree[now])
            elif jj<left or right<ii:
                continue
            else:
                qq.append([ii,jj,2*now+1,l+1])
                qq.append([ii,jj,2*now+2,l+1])
        min_list.append(min(s))
       
    for i in range(262142,-1,-1):
        if 2*i+1>=m:
            segtree[i]=n+1
        elif 2*i+2>=m:
            segtree[i]=segtree[2*i+1]
        else:
            segtree[i]=max(segtree[2*i+1],segtree[2*i+2])
    
    for i in range(n-k+2):
        qq=[[i,i+k-2,0,0]]
        s=set()
        while qq:
            ii,jj,now,l=qq.pop()
            kubun=2**l
            now2=now-kubun+1
            width=262144//kubun
            left=width*now2
            right=width*(now2+1)-1
            if ii<=left and right<=jj:
                s.add(segtree[now])
            elif jj<left or right<ii:
                continue
            else:
                qq.append([ii,jj,2*now+1,l+1])
                qq.append([ii,jj,2*now+2,l+1])
        max_list.append(max(s))
        
    cnt=0
    flag=[True]*(n-k+1)
    first=False
    for i in range(n-1):
        if x[i]<x[i+1]:
            cnt+=1
        else:
            cnt=0
        if cnt>=k-1:
            if first==False:
                first=True
            else:
                flag[i-k+2]=False
    
    for i in range(1,n-k+1):
        if x[i-1]<min_list[i] and max_list[i]<x[i+k-1]:
            flag[i]=False
            
    print(sum(flag))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    n,k=map(int,input().split())
    x=list(map(int,input().split()))
    
    min_list=[]
    max_list=[]
    m=262143+n
    segtree=[-1]*m
    
    for i in range(262143,m):
        segtree[i]=x[i-262143]
    	
    for i in range(262142,-1,-1):
        if 2*i+1>=m:
            segtree[i]=-1
        elif 2*i+2>=m:
            segtree[i]=segtree[2*i+1]
        else:
            segtree[i]=min(segtree[2*i+1],segtree[2*i+2])
    
    for i in range(n-k+2):
        qq=[(i,i+k-2,0,0)]
        s=set()
        while qq:
            ii,jj,now,l=qq.pop()
            kubun=2**l
            now2=now-kubun+1
            width=262144//kubun
            left=width*now2
            right=width*(now2+1)-1
            if ii<=left and right<=jj:
                s.add(segtree[now])
            elif jj<left or right<ii:
                continue
            else:
                qq.append((ii,jj,2*now+1,l+1))
                qq.append((ii,jj,2*now+2,l+1))
        min_list.append(min(s))
       
    for i in range(262142,-1,-1):
        if 2*i+1>=m:
            segtree[i]=n+1
        elif 2*i+2>=m:
            segtree[i]=segtree[2*i+1]
        else:
            segtree[i]=max(segtree[2*i+1],segtree[2*i+2])
    
    for i in range(n-k+2):
        qq=[(i,i+k-2,0,0)]
        s=set()
        while qq:
            ii,jj,now,l=qq.pop()
            kubun=2**l
            now2=now-kubun+1
            width=262144//kubun
            left=width*now2
            right=width*(now2+1)-1
            if ii<=left and right<=jj:
                s.add(segtree[now])
            elif jj<left or right<ii:
                continue
            else:
                qq.append((ii,jj,2*now+1,l+1))
                qq.append((ii,jj,2*now+2,l+1))
        max_list.append(max(s))
        
    cnt=0
    flag=[True]*(n-k+1)
    first=False
    for i in range(n-1):
        if x[i]<x[i+1]:
            cnt+=1
        else:
            cnt=0
        if cnt>=k-1:
            if first==False:
                first=True
            else:
                flag[i-k+2]=False
    
    for i in range(1,n-k+1):
        if x[i-1]<min_list[i] and max_list[i]<x[i+k-1]:
            flag[i]=False
            
    print(sum(flag))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))

pre_num = -1
k_sorted = 0
last = 0
for i in range(n):
  if p[i] > pre_num:
    last += 1
    if last == k:
      k_sorted += 1
  else:
    last = 1
  pre_num = p[i]
if k_sorted > 0:
  k_sorted -= 1

min_max = 0
for i in range(n - k):
  part = p[i : i + k + 1]
  min_k = min(part)
  max_k = max(part)
  if min_k == part[0] and max_k == part[-1]:
    min_max += 1
    
print(n - k + 1 - k_sorted - min_max)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
P = [-1] + list(map(int,input().split())) + [10**6]
Q = [''.join(map(str,P))]
for i in range(1,n-k+1):
    if (sorted(P[i-1:i+k-1])[1:k] != sorted(P[i:i+k])[0:k-1] or i==1 or i == n-k+1)and P[i:i+k] != sorted(P[i:i+k]):
        q = P[:i] + sorted(P[i:i+k]) + P[i+k:]
        Q += [''.join(map(str,q))]
print(len(Q))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
p = [int(x) for x in input().split()]
a = []
for j in range(N-K+1):
    tmp1 = sorted([p[i] for i in list(range(j,j+K))])
    tmp2 = [tmp1[i-j] if i in list(range(j,j+K)) else p[i] for i in p]
    a.append(tmp2)
b = len(set(map(tuple, a)))
print(b)

Submission status: Time Limit Exceeded

Solution code:
import math
from operator import itemgetter
import re
import sys
from itertools import accumulate
from collections import defaultdict
from collections import deque
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
input = sys.stdin.readline
N,K=map(int,input().split())
P = [int(i) for i in input().split()]
ans = N-K+1
bot = 0
if N == K:
    print(1)
else:
    for i in range(N-K):
        chk_array=P[i:i+K]
        chk_array2 = sorted(chk_array)
        if chk_array == chk_array2:
            if bot ==1:
                ans -= 1
            else:
                bot = 1
        else:
            if chk_array[0] == chk_array2[0]:
                if P[i+K] > chk_array2[-1]:
                    ans -=1
    if P[N-K:N] ==sorted(P[N-K:N]):
        if bot == 1:
            ans -=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

N, K = map(int, input().split())
A = list(map(int, input().split()))
cnt = 1
S = []
S.append(A)

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

for i in range(N-K):
    B = copy.deepcopy(A)
    B[i:i+K] = sorted(B[i:i+K])
    S.append(B)

print(len(get_unique_list(S)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, K = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]
f = False
l = deque(P[:K-1])
cnt = 0
c = deque([])
for i in range(1, len(l)):
    c.append(1 if l[i-1]<l[i] else -1)
ccnt = 0
new = l[-1]
for p in P[K-1:]:
  l.append(p)
  bigger = p > new
  c.append(1 if bigger else -1)
  maxL = max(l)
  pre = l.popleft()
  if sum(c)==K-1:
    ccnt += 1
    c.popleft()
    new = p
    if pre < min(l):
      f = True
    else:
      f = False
    continue
  if f and p == maxL:
    cnt += 1
  if pre < min(l):
    f = True
  else:
    f = False
  c.popleft()
  new = p
if ccnt > 1:
  cnt += ccnt - 1
print(N - K + 1 - cnt)

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int, input().split()))
p = list(map(int, input().split()))
s = set()
for i in range(a[0]-a[1]+1):
  tmp = p[:i] + sorted(p[i:i+a[1]]) + p[i+a[1]:]
  s.add(tuple(tmp))
print(len(s))

Submission status: Time Limit Exceeded

Solution code:
import copy

N,K = list(map(int, input().split()))
P = list(map(int, input().split()))
A = [[]] * (N-K+1)

for i in range(N-K+1):
    A[i] = copy.deepcopy(P)
    A[i][i : i+K] = sorted(A[i][i : i+K])

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

A = get_unique_list(A)

print(len(A))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
num,div= input().split()
num = int(num)
div = int(div)
if num != div:
  ar = np.array(list(map(int, input().split())))
  box = np.hstack(([str(np.hstack((np.sort(ar[:div]),ar[div:]))),str(np.hstack((ar[:num-div],np.sort(ar[num-div:]))))],np.array([str(np.hstack((ar[:i],np.sort(ar[i:i+div]),ar[i+div:]))) for i in range(1,num-div)])))
  print(len(np.unique(box)))
else:
  print(1)

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        diff = ''
        for i, v in enumerate(input().split()):
            if int(v) != i:
                diff += '1'
            else:
                diff += '0'

        ans = 0
        for i in range(N - K):
            if int(diff[i:i + K], 2) > 0:
                ans += 1
        print(max(1, ans))


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
P = [-1] + list(map(int,input().split())) + [2*(10**5)+1]
Q = [''.join(map(str,P))]
for i in range(1,n-k+1):
    q = P[:i] + sorted(P[i:i+k]) + P[i+k:]
    Q += [''.join(map(str,q))]
print(len(set(Q)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from bisect import insort_right as ir
from heapq import heapify, heappop as pop, heappush as push

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

P += [0]

# P2 = [-p for p in P]

# mid_min = P[:K]
# mid_max = P2[:K]

# heapify(mid_min)
# heapify(mid_max)

# ans = 0
# for i in range(N - K + 1):
#     if mid_min[0] != P[i] or mid_max[0] != P2[i + K]:
#         ans += 1
#     mid_min.remove(P[i])
#     mid_max.remove(P2[i])
#     push()
# print(ans)

left = []
middle = P[:K]
middle.sort()
right = deque(P[K:])
prev = tuple(left + middle + list(right))
ans = 0
flag = False
Pt = tuple(P)
for i in range(N - K + 1):
    # print(middle)
    if middle[-1] != P[i + K - 1] or middle[0] != prev[1]:
        ans += 1
        if middle == P[i : i+K]:
            if flag:
                ans -= 1
            flag = True
    prev = middle[:]
    # now = tuple(left + middle + list(right))
    # # print(now)
    # if prev != now:
    #     ans += 1
    # if now == Pt:
    #     if flag:
    #         ans -= 1
    #     flag = True
    # prev = now
    # # set_.add(tuple(left + middle + list(right)))
    # # set_.add(tuple(left + middle + P[K + 1:]))
    # left.append(P[i])
    middle.remove(P[i])
    # ir(middle, right.popleft())
    ir(middle, P[K + i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np

n,k = map(int, input().split())
p_list = tuple(map(int, input().split()))

p_before = 200001
up = 0

mins = [0]*(n+1-k)
maxs = [0]*(n+1-k)

for i in range(n+1-k):
    temp = p_list[i:i+k]
    mins[i] = min(temp)
    maxs[i] = max(temp)

mins = mins[:-1]
maxs = maxs[1:]

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == mins[i-k]:
            if p_list[i] != maxs[i-k]:
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)

Submission status: Time Limit Exceeded

Solution code:
import bisect 

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

A=P[:K]
A.sort()

B=[]
for i in range(N-K):
  B.append(P[:i]+A+P[i+K:])  
  A.remove(P[i])
  #print(A)
  bisect.insort(A,P[i+K])
  #print(A)
B.append(P[:N-K]+A+P[N:])
B.sort()

ans=1
for i in range(1,len(B)):
  if B[i]!=B[i-1]:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        q = queue.Queue()
        for v in input().split():
            q.put(int(v))

        diff = ''
        for i in range(N):
            if q.get() != N - 1 - i:
                diff += '1'
            else:
                diff += '0'
        ans = 0
        for i in range(N - K):
            if int(diff[i:i + K], 2) > 0:
                ans += 1
        print(max(1, ans))


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
p = [int(i) for i in input().split()]
cnt = 0 #ダブ1種
cnt2 = -1 #ダブ2種

for i in range(0,n-k):
    if p[i] < p[i+1]:
        if min(p[i:i+k]) == p[i]:
            if max(p[i+1:i+k+1]) == p[i+k]:
                cnt += 1
            elif sorted(p[i:i+k]) == p[i:i+k]:
                cnt2 += 1

if sorted(p[n-k:n]) == p[n-k:n]:
    cnt2 += 1

if cnt2 > 0:
    ans = n-k+1-cnt-cnt2
else:
    ans = n-k+1-cnt
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:

n, k = map(int, input().split())
p = list(map(int, input().split()))

buf1 = []

for i in range(n - k + 1):
    buf = p[:i] + sorted(p[i:k+i]) + p[k+i:]
    if not buf in buf1:
        buf1.append(buf)

print(len(buf1))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N,K=[int(x) for x in input().split(" ")]
n=[int(x) for x in input().split(" ")]
t=set()
for i in range(N-K+1):
    t.add(tuple(n[:i]+sorted(n[i:i+K])+n[i+K:]))
print(len(t))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
P = [-1] + list(map(int,input().split())) + [10**6]
Q = [''.join(map(str,P))]
for i in range(1,n-k+1):
    q = P[:i] + sorted(P[i:i+k]) + P[i+k:]
    Q += [''.join(map(str,q))]
print(len(set(Q)))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
p_list = tuple(map(int, input().split()))

p_before = 200001
up = 0

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == min(p_list[(i-k):i]):
            if p_list[i] != max(p_list[(i-k+1):(i+1)]):
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)