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 = list(map(int, input().split()))
P = list(map(int, input().split()))

###############################################################################
# AVL木サンプルコード
###############################################################################

###############################################################################
# 共通定義
###############################################################################

class Node: # ノードの型
    def __init__(self, height, key, x):
        self.height = height # そのノードを根とする部分木の高さ
        self.key    = key    # そのノードのキー
        self.value  = x      # そのノードの値
        self.lst    = None   # 左部分木
        self.rst    = None   # 右部分木

# 部分木 t の高さを返す
def height(t): return 0 if t is None else t.height

# 左右の部分木の高さの差を返す。左が高いと正、右が高いと負
def bias(t): return height(t.lst) - height(t.rst)

# 左右の部分木の高さから、その木の高さを計算して修正する
def modHeight(t): t.height = 1 + max(height(t.lst), height(t.rst))

def rotateL(v): # ２分探索木 v の左回転。回転した木を返す
    u = v.rst; t2 = u.lst
    u.lst = v; v.rst = t2
    modHeight(u.lst)
    modHeight(u)
    return u
def rotateR(u): # ２分探索木 u の右回転。回転した木を返す
    v = u.lst; t2 = v.rst
    v.rst = u; u.lst = t2
    modHeight(v.rst)
    modHeight(v)
    return v
def rotateLR(t): # ２分探索木 t の二重回転(左回転 -> 右回転)。回転した木を返す
    t.lst = rotateL(t.lst)
    return rotateR(t)
def rotateRL(t): # ２分探索木 t の二重回転(右回転 -> 左回転)。回転した木を返す
    t.rst = rotateR(t.rst)
    return rotateL(t)

###############################################################################
# AVL木マップクラス
###############################################################################

class AVLMap:
    def __init__(self):
        self.root   = None  # AVL木の根。Node 型
        self.change = False # 修正が必要かを示すフラグ(True:必要, False:不要)
        self.lmax   = None  # 左部分木のキーの最大値
        self.value  = None  # lmax に対応する値

    ###########################################################################
    # バランス回復
    ###########################################################################

    # 挿入時の修正(balanceLi:左部分木への挿入, balanceRi:右部分木への挿入)
    def balanceLi(self, t): return self.balanceL(t)
    def balanceRi(self, t): return self.balanceR(t)

    # 削除時の修正(balanceLd:左部分木での削除, balanceRd:右部分木での削除)
    def balanceLd(self, t): return self.balanceR(t)
    def balanceRd(self, t): return self.balanceL(t)

    # 部分木 t のバランスを回復して戻り値で返す
    # 左部分木への挿入に伴うAVL木の修正
    # 右部分木での削除に伴うAVL木の修正
    def balanceL(self, t):
        if not self.change: return t
        h = height(t)
        if bias(t) == 2:
            if bias(t.lst) >= 0:
                t = rotateR(t)
            else:
                t = rotateLR(t)
        else: modHeight(t)
        self.change = (h != height(t))
        return t

    # 部分木 t のバランスを回復して戻り値で返す
    # 右部分木への挿入に伴うAVL木の修正
    # 左部分木での削除に伴うAVL木の修正
    def balanceR(self, t):
        if not self.change: return t
        h = height(t)
        if bias(t) == -2:
            if bias(t.rst) <= 0:
                t = rotateL(t)
            else:
                t = rotateRL(t)
        else: modHeight(t)
        self.change = (h != height(t))
        return t

    ###########################################################################
    # insert(挿入)
    ###########################################################################

    # エントリー(key, x のペア)を挿入する
    def insert(self, key, x): self.root = self.insert_sub(self.root, key, x)

    def insert_sub(self, t, key, x):
        if t is None:
            self.change = True
            return Node(1, key, x)
        elif key < t.key:
            t.lst = self.insert_sub(t.lst, key, x)
            return self.balanceLi(t)
        elif key > t.key:
            t.rst = self.insert_sub(t.rst, key, x)
            return self.balanceRi(t)
        else:
            self.change = False
            t.value = x
            return t

    ###########################################################################
    # delete(削除)
    ###########################################################################

    # key で指すエントリー(ノード)を削除する
    def delete(self, key): self.root = self.delete_sub(self.root, key)

    def delete_sub(self, t, key):
        if t is None:
            self.change = False
            return None
        elif key < t.key:
            t.lst = self.delete_sub(t.lst, key)
            return self.balanceLd(t)
        elif key > t.key:
            t.rst = self.delete_sub(t.rst, key)
            return self.balanceRd(t)
        else:
            if t.lst is None:
                self.change = True
                return t.rst # 右部分木を昇格させる
            else:
                t.lst = self.delete_max(t.lst) # 左部分木の最大値を削除する
                t.key = self.lmax # 左部分木の削除した最大値で置き換える
                t.value = self.value
                return self.balanceLd(t)

    # 部分木 t の最大値のノードを削除する
    # 戻り値は削除により修正された部分木
    # 削除した最大値を lmax に保存する
    def delete_max(self, t):
        if t.rst is not None:
            t.rst = self.delete_max(t.rst)
            return self.balanceRd(t)
        else:
            self.change = True
            self.lmax = t.key # 部分木のキーの最大値を保存
            self.value = t.value
            return t.lst # 左部分木を昇格させる

    ###########################################################################
    # member(検索)等
    ###########################################################################
    def max(self):
        return self.max_sub(self.root)
 
    def max_sub(self, t):
        if t.rst is not None:
            return self.max_sub(t.rst)
        else:
            return t.value #key
          
    def min(self):
        return self.min_sub(self.root)
    
    def min_sub(self, t):
        if t.lst is not None:
            return self.min_sub(t.lst)
        else:
            return t.value #key
        
    # キーの検索。ヒットすれば True、しなければ False
    def member(self, key):
        t = self.root
        while t is not None:
            if key < t.key:
                t = t.lst
            elif key > t.key:
                t = t.rst
            else:
                return True
        return False

    # キーから値を得る。キーがヒットしない場合は None を返す
    def lookup(self, key):
        t = self.root
        while t is not None:
            if key < t.key:
                t = t.lst
            elif key > t.key:
                t = t.rst
            else:
                return t.value
        return None

    # マップが空なら True、空でないなら False
    def isEmpty(self): return self.root is None

    # マップを空にする
    def clear(self): self.root = None

    # キーのリスト
    def keys(self): return keys_sub(self.root)

    # 値のリスト
    def values(self): return values_sub(self.root)

    # エントリーのリスト
    def items(self): return items_sub(self.root)

    # マップのサイズ
    def size(self): return len(self.keys())

    def __contains__(self, key): self.member(key)
    def __getitem__(self, key): return self.lookup(key)
    def __setitem__(self, key, x): return self.insert(key, x)
    def __delitem__(self, key): self.delete(key)
    def __bool__(self): return not self.isEmpty()
    def __len__(self): return self.size()
    def __iter__(self): return iter(self.keys())

    ###########################################################################
    # Debug 用メソッド
    ###########################################################################

    # AVL木をグラフ文字列に変換する
    def __str__(self): return toGraph("", "", self.root).rstrip()

    # AVL木のバランスが取れているか確認する
    def balanced(self): return balanced(self.root)

    # ２分探索木になっているか確認する
    def bstValid(self): return bstValid(self.root)

###############################################################################
# 作業メソッド
###############################################################################

def keys_sub(t):
    if t is None: return []
    return keys_sub(t.lst) + [t.key] + keys_sub(t.rst)

def values_sub(t):
    if t is None: return []
    return values_sub(t.lst) + [t.value] + values_sub(t.rst)

def items_sub(t):
    if t is None: return []
    return items_sub(t.lst) + [(t.key, t.value)] + items_sub(t.rst)

  
  
m = AVLMap()

for p in P[:K]:
    m[p] = p

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

c = 0
pre = False
for d in decending[:-K+1]:
    if d >= K:
        if not pre:
            c += 1
        pre = True
    else:
        pre = False

ans = 1

for i in range(N-K):
    #print(P[i], m.min(), m.max(), decending[i])
    if m.min() == P[i] and m.max() < P[i+K]:
        ans += 0
    else:
        ans += 1
    m.delete(P[i])
    m.insert(P[i+K],P[i+K])
  
if c>1:
    ans -= c-1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
#! //Users/daigofujiwara/anaconda3/bin python3

#h行で列和がyかy+1であるかどうかとサンプルを出力

input1=input()
input2=input()
N,K=input1.split(" ")
N,K=int(N),int(K)
P=input2.split(' ')
P = [int(n) for n in P]

list=[]

for i in range(N-K+1):
    temp=P[i:i+K]
    PP=copy.copy(P)
    temp.sort()
    k=0
    for j in range(i,i+K):
        PP[j]=temp[k]
        k+=1
    if not (PP in list):
        list.append(PP)

print(len(list))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
li = list(map(int,input().split()))
al=[]
for i in range(n-k+1):
    ans=li[i:i+k]
    l=li[:]
    l[i:i+k]=sorted(ans)
    al.append(l)    
al.append(0)
ans=0
for i in range(n-k+1):
    ans+=1
    if(al[i] in al[i+1:]):
      ans-=1
      

print(ans)

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
pp=p[0:k]
pp_s=np.sort(pp)

for i in range(len(pp)):
    if pp_s[i]!=pp[i]:
        for i in range(len(pp)-1):
            if pp[k-1-i]<pp[k-2-i]:
                seq=i+1
        break
    if i==len(pp)-1:
        if first==0:
            first+=1
            seq=k
ma=np.max(pp)
mi=np.min(pp)

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        P = list(map(int, input().split()))

        diff = ''
        for i in range(N):
            if P.pop() != 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:
# -*- coding:utf8 -*-

n,k = map(int, input().split())
p = list(map(int, input().split()))
all = set()
all.add(''.join(map(str,p)))
for i in range(n - k):
    c = p[:i] + sorted(p[i:i+k]) + p[i+k:]
    all.add(''.join(map(str,c)))
print(len(all))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

def main():
    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))





















if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

asc_cum = [0]
for p,q in zip(P,P[1:]):
    asc_cum.append(asc_cum[-1] + int(p<q))

all_asc = []
for i in range(K-1,N):
    all_asc.append(asc_cum[i] - asc_cum[i-K+1] == K-1)

INF = float('inf')
class SegTreeMin:
    def __init__(self,arr):
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [INF]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = min(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i:
            i = (i-1)//2
            self.nodes[i] = min(self.nodes[2*i+1],self.nodes[2*i+2])

    def query(self,a,b,k=0,l=0,r=-1):
        if r < 0: r = self.n
        if r <= a or b <= l: return INF
        if a <= l and r <= b: return self.nodes[k]
        return min(self.query(a,b,2*k+1,l,(l+r)//2), self.query(a,b,2*k+2,(l+r)//2,r))

class SegTreeMax:
    def __init__(self,arr):
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [-1]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = max(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i:
            i = (i-1)//2
            self.nodes[i] = max(self.nodes[2*i+1],self.nodes[2*i+2])

    def query(self,a,b,k=0,l=0,r=-1):
        if r < 0: r = self.n
        if r <= a or b <= l: return -1
        if a <= l and r <= b: return self.nodes[k]
        return max(self.query(a,b,2*k+1,l,(l+r)//2), self.query(a,b,2*k+2,(l+r)//2,r))

segt_min = SegTreeMin(P)
segt_max = SegTreeMax(P)

first_asc = False
ans = 0
for i,asc in enumerate(all_asc):
    if not asc:
        if i>0:
            #print(i,segt_min.query(i,i+K-1),segt_max.query(i,i+K-1))
            #if min(P[i:i+K-1]) > P[i-1] and max(P[i:i+K-1]) < P[i+K-1]:
            if segt_min.query(i,i+K-1) > P[i-1] and segt_max.query(i,i+K-1) < P[i+K-1]:
                continue
        ans += 1
        continue
    if not first_asc:
        first_asc = True
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        P = list(map(int, input().split()))

        diff = ''
        for i in range(N):
            if P[i] != 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 = list(map(int, input().split()))

ans = 0
same_flag = True

for i in range(n - k + 1):
    same_len = 0
    temp = p[i:i + k]
    for j in range(i, i + k - 1):
        if p[j] < p[j + 1]:
            same_len += 1
            continue
        else:
            ans += 1
            break
    if same_flag and same_len == k - 1:
        ans += 1
        same_flag = False
    if same_len < k - 1:
        if i + k < n and p[i] == min(temp) and p[i + k] > max(temp):
            ans -= 1
            continue
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
#import numpy as np
#s=np.zeros((n-k,n))
s=[]
for i in range(n-k+1):
    s.append(tuple(p[:i]+sorted(p[i:i+k])+p[i+k:]))
print(len(set(tuple(s))))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
p = list(map(int, input().split()))
cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  hea = set(p[i:i + K])
  heap = sorted(hea)
  range_min = heap[0]
  range_max = heap[-1]
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if range_min == l and range_max == r:
    sortMatchFlg = p[i:i + K] == heap
    if sortMatchFlg:
      sortMatchCnt += 1                      

  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  # preR = r
  prerange_min = range_min
  # prerange_max = range_max
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)

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 = [str(np.hstack((np.sort(ar[:div]),ar[div:]))),str(np.hstack((ar[:num-div],np.sort(ar[num-div:]))))]
  for i in range(1,num-div):
    box.append(str(np.hstack((ar[:i],np.sort(ar[i:i+div]),ar[i+div:]))))
  print(len(np.unique(box)))
else:
  print(1)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
A = []
for i in range(1,N-K+1):
    A.append((min(P[i:i+K-1]),max(P[i:i+K-1])))
B = {}
cur = 0
for i in range(1,N):
    if P[i]<P[i-1]:
        if i-cur>=K:
            B[cur] = i-cur
        cur = i
if N-cur>=K:
    B[cur] = N-cur
d = 0
if len(B)>1:
    d = len(B)-1
cnt = 1
for i in range(K,N):
    if P[i]<A[i-K][1] or P[i-K]>A[i-K][0]:
        cnt += 1
print(cnt-d)

Submission status: Time Limit Exceeded

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

l = [0]*(N-1)
for i in range(len(l)):
    if P[i]>=P[i+1]:
        l[i] = 1
l2 = [0]*(N-K+1)
for i in range(len(l2)):
    if sum(l[i:i+K-1])==0:
        l2[i]=1
        
for i in range(N-K+1):
    if l2[i]==1:
        if first == 1:
            count += 1
            first = 0
        continue
    elif (i!=0) and (P[i-1] < min(P[i:i+K-1])) and (P[i+K-1] > max(P[i:i+K-1])):
        continue
    else:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
P = [int(i) for i in input().split()]

answer_ex = list()

for num in range(N - K +1):
    P_test = P.copy()
    sort_P=[]
    for i in range(num,K + num):
        sort_P.append(P_test[i])
    sort_P.sort()
    for inum in range(num,K + num):
        P_test[inum] = sort_P[inum - num]
    answer_ex.append(P_test)
    if answer_ex.count(P_test)>=2:
     	del answer_ex[-1]

print(len(answer_ex))

Submission status: Time Limit Exceeded

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

ans = 0
same_flag = True

for i in range(n - k + 1):
    same_len = 0
    temp = p[i:i + k]
    if i + k < n and p[i] == min(temp) and p[i + k] > max(temp):
        continue
    for j in range(i, i + k - 1):
        if p[j] < p[j + 1]:
            same_len += 1
            continue
        else:
            ans += 1
            break
    if same_flag and same_len == k - 1:
        ans += 1
        same_flag = False
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy

N,K = map(int, input().split())
P = list(map(int, input().split()))
row =[]
newrow = []
rowpart = []
rowmax = int(0)
anslist = [[]]
ans = int(0)

for i in range(N-1):
    if P[i]<P[i+1]:
        row.append(1)
    else:
        row.append(0)

for i in range(N-K+1):
    newrow = row[:]
    rowpart = P[i:i+K]
    for j in range(i,i+K-1):
        newrow[j] = 1

#        print(newrow)
#        print(i)
#    print(rowpart)
    if newrow not in anslist:
        ans +=1
        anslist.append(newrow)
    else:
        if rowmax == max(rowpart):
            ans +=1

    rowmax = max(rowpart)

#print(row)
#print(anslist)

print(min(ans,N-K+1))

Submission status: Time Limit Exceeded

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

ans = 0
an_l = []
for i in range(N-K+1):
    P2 = copy.deepcopy(P)
    P2[i:i+K] = sorted(P2[i:i+K])
    if P2 not in an_l:
        an_l.append(P2)       

print(len(an_l))

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])
    
    def search(i,j,now):
        for k in range(20):
            if 2**k-1<=now<2**(k+1)-1:
                break
        kubun=2**k
        now2=now-kubun+1
        width=262144//kubun
        left=width*now2
        right=width*(now2+1)-1
        if i<=left and right<=j:
            return segtree[now]
        elif j<left or right<i:
            return n+1
        else:
            return min(search(i,j,2*now+1),search(i,j,2*now+2))
    
    for i in range(n-k+2):
        min_list.append(search(i,i+k-2,0))
       
    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])
    
    def search(i,j,now):
        for k in range(20):
            if 2**k-1<=now<2**(k+1)-1:
                break
        kubun=2**(k)
        now2=now-kubun+1
        width=262144//kubun
        left=width*now2
        right=width*(now2+1)-1
        if i<=left and right<=j:
            return segtree[now]
        elif j<left or right<i:
            return -1
        else:
            return max(search(i,j,2*now+1),search(i,j,2*now+2))
    
    for i in range(n-k+2):
        max_list.append(search(i,i+k-2,0))
        
    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 insert(target_list, target):
  region = [0, len(target_list)-1]
  while region[0] < region[1]:
    i = (region[0] + region[1]) // 2
    if target_list[i] < target and target < target_list[i+1]:
      target_list.insert(i+1, target)
      return
    if target_list[i] > target:
      region[1] = (region[0] + region[1]) // 2
    if target_list[i+1] < target:
      region[0] = (region[0] + region[1]) // 2 + 1

  target_list.append(target)

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

res_set = set()

target = []
for i in range(N - K + 1):
  if i == 0:
    target = P[i:i+K]
    target.sort()
  else:
    target.remove(P[i-1])
    insert(target, P[i+K-1])
  new_list = P[:i] + target + P[i+K:]
  res_set.add(tuple(new_list))

#print(res_set)
print(len(res_set))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = 0
flag = 0
for i in range(N - K + 1):
    tmp = P[i:i + K]
    if tmp != sorted(tmp):
        ans += 1
        flag += 1
        if i < N - K:
            if P[i] <= min(tmp) and P[i + K] >= max(tmp):
                ans -= 1
if flag != N - K + 1:
    ans += 1
print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
def counting_sort(A, k):
    B=[0]*(len(A)+1)
    C=[0]*(k+1)
    for a in A:
        C[a]+=1
    for i in range(1, k+1):
        C[i]+=C[i-1]
    for a in A[::-1]:
        B[C[a]]=a
        C[a]-=1
    return B
  
N, K=map(int, input().split())
P=list(map(int, input().split()))+[-1]
ans=N-K+1
flag=True
for i in range(N-K+1):
  tmp=counting_sort(P[i:i+K], N)[1:]
  if tmp[0]==P[i] and tmp[-1]<P[i+K]:
    ans-=1
  elif tmp==P[i:i+K]:
    if flag:
      flag=False
    else:
      ans-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    num, sortNum = [int(i) for i in input().split()]
    targetList = [int(i) for i in input().split()]
    answerList = []
    for idx in range(num - sortNum + 1):
        tmpList = targetList[:idx] + sorted(targetList[idx:idx+sortNum]) + targetList[idx+sortNum:]
        if (tmpList in answerList) == False:
            answerList.append(tmpList)
    print(len(answerList))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf8 -*-

n,k = map(int, input().split())
p = list(map(int, input().split()))
ans = 1
all = [p]
for i in range(n - k):
    c = p[:i] + sorted(p[i:i+k]) + p[i+k:]
    if c not in all:
        ans += 1
        all.append(c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
n,k=map(int, input().split())
p=list(map(int, input().split()))
porigin=copy.copy(p)
pprevious=copy.copy(p)
#print(porigin)
#print(pprevious)
count=0
countorigin=0
for i in range(n-k+1):
    p=copy.copy(porigin)
    pdash=copy.copy(p[i:i+k])
    pdash.sort()
    for j in range(k):
        p[i+j]=pdash[j]
    #print(p)
    if p==pprevious:
        count+=1
    elif p==porigin:
        countorigin+=1
    else:
        pprevious=copy.copy(p)
answer=n-k+1-count
if countorigin>=2:
    answer-=(countorigin-1)
if answer==0:
    answer=1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
a = [ int(i) for i in input().split(" ") ]
b = [ int(i) for i in input().split(" ") ]

N=a[0]
K=a[1]

s=[]
s.append(b)

for i in range(N-K):
  u=[]
  t=[]
  for j in range(K):
    t.append(b[i+j])
  t.sort()
  #print(t)
  
  for k in range(i):
    u.append(b[k])
  for j in range(K):
    u.append(t[j])
  for l in range(i+K,N):
    u.append(b[l])
  s.append(u)

#print(s)

x=set(list(map(tuple,s)))
#print(x)
print(len(x))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
p_list = list(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 sys
input = sys.stdin.readline
def main():
    num, sortNum = [int(i) for i in input().split()]
    targetList = [int(i) for i in input().split()]
    answerList = []
    for idx in range(num - sortNum + 1):
        tmpList = targetList[:idx] + sorted(targetList[idx:idx+sortNum]) + targetList[idx+sortNum:]
        tmpStr = ','.join([str(i) for i in tmpList])
        if (tmpStr in answerList) == False:
            answerList.append(tmpStr)
    print(len(answerList))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
if N == K:
    print(1)
    exit()
P = list(map(int,input().split()))
S = set()


m = min(P[ : K])
M = max(P[ : K])
for i in range(N-K+1):
    if m == P[i] and M < P[i+K+1]:
        M = P[i+K+1]
        m = min(P[i : i+K])
        continue
    _ = P[:i] + sorted(P[i : i+K]) + P[i+K : ]
    S.add(tuple(_))
print(len(S))

Submission status: Time Limit Exceeded

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

dic = {}
for i in range(n-k+1):
    new_p = p[:i] + sorted(p[i:i+k]) + p[i+k:]
    dic[str(new_p)] = True
print(len(dic))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        P = list(map(int, input().split()))

        sorted_p = sorted(P)
        cnt = 0
        diff = ''
        for i in range(N):
            if P[i] != sorted_p[i]:
                cnt += 1
                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:
import sys
input = sys.stdin.readline

import numpy as np

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

    li = []

    for i in range(n - k + 1):
        li.append(p[:i] + sorted(p[i:k+i]) + p[k+i:])

    print(len(list(map(list, set(map(tuple, li))))))



















if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    num, sortNum = [int(i) for i in input().split()]
    targetList = [int(i) for i in input().split()]
    answerList = []
    for idx in range(num - sortNum + 1):
        tmpList = targetList[:idx] + sorted(targetList[idx:idx+sortNum]) + targetList[idx+sortNum:]
        tmpStr = ','.join([str(i) for i in tmpList])
        if (tmpStr in answerList) == False:
            answerList.append(tmpStr)
    print(len(answerList))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
p = (n - k) + 1
c = []
for i in range(p):
  b = a.copy()
  b[i: i+k] = sorted(set(b[i: i+k]))
  if b not in c:
    c.append(b)
print(len(c))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N, K =[int(x) for x in input().split(" ")]
nums = [int(x) for x in input().split(" ")]
tuples = set()

for i in range(N-K+1):
    l = nums[:i] + sorted(nums[i:i+K]) + nums[i+K:]
    lt = tuple(l)
    tuples.add(lt)

print(len(tuples))