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: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
flag = False
i = k-1
sc = 0
while i >=1 and (p[i] > p[i-1]):
  sc += 1
  i -= 1
if sc == k-1:
  flag = True
  count = n-k
else:
  count = n-k+1
for j in range(n-k):
  if p[k+j] < p[k+j-1]:
    sc = 0
  else:
    sc += 1
    if sc >= k-1:
      flag = True
      count -= 1
    if max(p[j+1:k+j+1])==p[k+j] and min(p[j:k+j])==p[j]:
      count -= 1
print(count+int(flag))

Submission status: Wrong Answer

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

sorted_p = []
num = 1

for i in range(n-k+1):
  if sorted(p[0+i:k+i]) != p[0+i:k+i]:
    num += 1
print(num)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
p = list(map(int, input().split()))
cnt = 1
preL = p[0]
# preR = p[K - 1]
prerange_min = min(p[0:0 + K])
# prerange_max = max(p[0:0 + K])
sortMatchCnt = 0
for i in range(1, N - K + 1):
#  print(p[i:i + K])
  range_min = min(p[i:i + K])
  range_max = max(p[i:i + K])
  l = p[i]
  r = p[i + K - 1]
  sortMatchFlg = p[i:i + K] == sorted(p[i:i + K])
  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: Wrong Answer

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 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]:
            cnt += 1

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

print(ans)

Submission status: Wrong Answer

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]:
        break
    if i==len(pp)-1:
        if first==0:
            count-=1
            first+=1

for i in range(1,n-k+1):
    pp=p[i:i+k]
    if p[i-1]<=np.min(pp) and pp[k-1]==np.max(pp):
        count-=1
    elif pp[0]==min(pp) and pp[k-1]==max(pp):
        pp_s=np.sort(pp)
        for i in range(len(pp)):
            if pp_s[i]!=pp[i]:
                break
            if i==len(pp)-1:
                if first==0:
                    first+=1
                    count-=1

print(count)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush

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

increases = [int(p1 < p2) for p1, p2 in zip(ppp, ppp[1:])]
h = k - 1
tmp = sum(increases[:h])
duplicated = [0] * n
for i, q in enumerate(increases[h:], start=h):
    tmp += q - increases[i - h]
    if tmp == h:
        duplicated[i + 1] = 1

state = [1] * k + [0] * (n - k)
ans = 1
minq = ppp[:k]
maxq = [-p for p in ppp[:k]]
heapify(minq)
heapify(maxq)

for i, p in enumerate(ppp[k:], start=k):
    l = ppp[i - k]

    if l == minq[0] and p > -maxq[0]:
        pass
    elif duplicated[i] == 1:
        pass
    else:
        ans += 1
    state[l] = 2
    state[p] = 1
    while state[minq[0]] == 2:
        heappop(minq)
    while state[-maxq[0]] == 2:
        heappop(maxq)
    heappush(minq, p)
    heappush(maxq, -p)
    # print(i, p, ans)
    # print(state)
    # print(minq)
    # print(maxq)

print(ans)

Submission status: Wrong Answer

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

ans = N - K

if N == K:
  ans += 1
  
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
d = 0
q = deque()
for i in range(K):
    if len(q) == 0:
        q.append(i)
    else:
        while len(q) > 0:
            if a[q[len(q)-1]] > a[i]:
                q.pop()
            else:
                q.append(i)
                break
        else:
            q.append(i)


for i in range(K, N):
    if len(q) == 0:
        q.append(i)
    else:
        flag = 0
        while len(q) > 0:
            if a[q[len(q)-1]] > a[i]:
                q.pop()
                flag = 1
            else:
                q.append(i)
                break
        else:
            q.append(i)
        if q[0] == i-K:
            l = q.popleft()
        else:
            flag = 1
        if flag == 1:
            ans += 1


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')


def main():
	N,k=map(int,input().split())

	p=list(map(int,input().split()))
	q=[n*(-1) for n in p]
	cnt=1

	for i in range(N-k-1):
		heapq.heapify(p[i:i+k])
		heapq.heapify(q[i+1:i+k+1])
		if heapq.heappop(p[i:i+k])==p[i] and heapq.heappop(q[i+1:i+k+1])==q[i+k+1]:
			cnt+=0
		else:
			cnt+=1
	print(cnt)

if __name__=='__main__':
	main()

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
*P,=map(int,input().split())
a=b=0
def is_sorted(Kr):
    return all(i<j for i,j in zip(Kr,Kr[1:]))
for i,j in zip(range(N),range(K,N)):
    a+=P[i]>min(P[i:j])or P[j]<max(P[i:j])
for i in range(N-K+1):
    b+=is_sorted(P[i:i+K])
print(1+a+(1-b)*(b>0))

Submission status: Wrong Answer

Solution code:

import heapq

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

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

minlis = []
maxlis = []
endflag = [False] * N

ans = 1

for i in range(K):

    heapq.heappush(minlis,P[i])
    heapq.heappush(maxlis,-1 * P[i])

for i in range(N - K):

    flag = False

    endflag[P[i]] = True
    if minlis[0] != P[i]:
        flag = True

    while endflag[minlis[0]]:
        heapq.heappop(minlis)

    if P[i+K] <= -1 * maxlis[0]:
        flag = True

    while endflag[-1 * maxlis[0]]:
        heapq.heappop(maxlis)

    

    heapq.heappush(minlis,P[i+K])
    heapq.heappush(maxlis,-1 * P[i+K])



    if flag:
        ans += 1

kaburi = 0
P.append(-2)
now = 0
nmax = -1
for i in range(N+1):
    if nmax < P[i]:
        now += 1
        nmax = P[i]
    else:
        kaburi += max(0 , now - K + 1)
        now = 1
        nmax = P[i]
        

kaburi = max(0,kaburi - 1)
print (ans - kaburi)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    #間違ってるところを区間に含む/この含んでいるのが違うなら、あれですよと
    N,K = MI()
    P = LI()
    wrongs=deque()
    including = deque()
    for i in range(N-1):
        if P[i]>P[i+1]:
            wrongs.append(i+0.5)
    including=deque()
    for w in deepcopy(wrongs):
        if w < K-1:
            including.append(wrongs.popleft())
        else:
            break
    ans = 1
    zero_experiense = not including
    for left in range(N-K+1):
        right=left+K-1
        update = False
        if including and including[0]<left:
            update = True
            including.popleft()
        if wrongs and wrongs[0]<right:
            update = True
            including.append(wrongs.popleft())
        if update:
            if not including:
                if zero_experiense:
                    continue
                else:
                    zero_experiense=True
            ans += 1
    print(ans)
        



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush

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

state = [1] * k + [0] * (n - k)
ans = 1
minq = ppp[:k]
maxq = [-p for p in ppp[:k]]
heapify(minq)
heapify(maxq)

for i, p in enumerate(ppp[k:], start=k):
    l = ppp[i - k]

    if l == minq[0] and p > -maxq[0]:
        pass
    else:
        ans += 1
    state[l] = 2
    state[p] = 1
    while state[minq[0]] == 2:
        heappop(minq)
    while state[-maxq[0]] == 2:
        heappop(maxq)
    heappush(minq, p)
    heappush(maxq, -p)
    # print(i, p, ans)
    # print(state)
    # print(minq)
    # print(maxq)

increases = [int(p1 < p2) for p1, p2 in zip(ppp, ppp[1:])]
h = k - 1
tmp = sum(increases[:h])
duplicated = 0
if tmp == h:
    duplicated += 1
for i, q in enumerate(increases[h:], start=h):
    tmp += q - increases[i - h]
    if tmp == h:
        duplicated += 1
duplicated = max(0, duplicated - 1)

print(ans - duplicated)

Submission status: Wrong Answer

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

if N == K:
    # 組み合わせは 1 つ
    print(1)
else:
    sets = set()
    for i in range(N-K+1):
        part = Pn[i:K+i]
        part.sort()
        t = tuple(Pn[0:i] + part + Pn[i+K:K+K+i])
        sets.add(t)
    
    print(len(sets))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
*P,=map(int,input().split())
a=b=0
for i,j in zip(range(N),range(K,N)):
    a+=P[i]>min(P[i:j])or P[j]<max(P[i:j])
for i in range(N-K+1):
    b+=P[i:i+K]==sorted(P[i:i+K])
print(1+a+(1-b)*(b>0))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from itertools import accumulate
n, k = map(int, input().split())
p = list(map(int, input().split()))
d = [p[i] > p[i + 1] for i in range(n - 1)]
s = list(accumulate(d))
ans = 1
for i in range(n - k - 1):
    if s[i + k] - s[i] < k:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
P =  list(map(int,input().split()))
if N==K:
  print(1);exit()
else:
  ans = N-K+1
  for i in range(len(P)):
    if i+K < N-1:
      small = P[i:i+K+1]
      small2 = P[i:i+K]
      if small[0] == min(small) and small[-1] == max(small):
        ans -= 1
      if small2 == sorted(small2):
        ans -= 1
    
print(ans)

Submission status: Wrong Answer

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

ordered = []
ret = 0

for i in range(k-1):
    if p[i] < p[i+1]:
        ordered.append(True)
    else:
        ordered.append(False)

for i in range(k-1, n-1):
    
    
    if p[i] < p[i+1]:
        ordered.append(True)
    else:
        ordered.append(False)
        
    tf = list(set(ordered))

    if (len(tf) == 1) & (tf[0] == True):
        pass
    else:
        ret += 1
    ordered.pop(0)
    
    
print(max(ret, 1))

Submission status: Wrong Answer

Solution code:
import sys

pos=input()
pos=pos.split()
N=int(pos[0])
K=int(pos[1])

J=input()
J=J.split()
J=[int(item) for item in J]
index=0
indexset=[]
Jtemp=[]
for i in range(0,N-K+1):
    Jtemp[:]=J[:]
    temp=Jtemp[index:index+K]
    temp.sort()
    Jtemp[index:index+K]=temp
    indexset.append(Jtemp)
    index+=1
    
print(len(indexset))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
d = 0
q = deque()
for i in range(K):
    if len(q) == 0:
        q.append(i)
    else:
        while len(q) > 0:
            if a[q[len(q)-1]] >= a[i]:
                q.pop()
            else:
                q.append(i)
                break
        else:
            q.append(i)


for i in range(K, N):
    if len(q) == 0:
        q.append(i)
    else:
        flag = 0
        while len(q) > 0:
            if a[q[len(q)-1]] >= a[i]:
                q.pop()
                flag = 1
            else:
                q.append(i)
                break
        else:
            q.append(i)
        if a[q[0]] < a[i-K]:
            flag = 1
        if flag == 1:
            ans += 1
        if q[0] == i-K:
            q.popleft()

print(ans)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    #間違ってるところを区間に含む/この含んでいるのが違うなら、あれですよと
    N,K = MI()
    P = LI()
    wrongs=deque()
    including = deque()
    for i in range(N-1):
        if P[i]>P[i+1]:
            wrongs.append(i+0.5)
    including=deque()
    for w in deepcopy(wrongs):
        if w < K-1:
            including.append(wrongs.popleft())
        else:
            break
    ans = 1
    for left in range(N-K+1):
        right=left+K-1
        update = False
        if including and including[0]<left:
            update = True
            including.popleft()
        if wrongs and wrongs[0]<right:
            update = True
            including.append(wrongs.popleft())
        if update:
            ans += 1
    print(ans)
        



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=[int(i) for i in input().split()]
l=list(range(n))
ans=0
import bisect
for i in p:
    n=bisect.bisect_left(l,i)
    ans+=n
    del l[n]
if ans==0:
    print(1)
    exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
n,k=map(int,input().split())
l=list(map(int,input().split()))
now=sorted(l[:k])
now_max=now[-1]
now_min=now[0]
ans=1
for i in range(n-k):
  if l[k+i]>now_max and l[i]==now_min:
    now=now[1:]+[l[k+i]]
    now_max=l[k+i]
    now_min=now[0]
  else:
    ans+=1
    now=now[1:]
    bisect.insort_left(now,l[k+i])
    now_max=now[-1]
    now_min=now[0]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n,k=map(int,input().split())
p=list(map(int,input().split()))
if k==n:
  print(1)
  sys.exit()
ct=1
for i in range(1,n-k):
  if min(p[i:i+k+1])!=p[i] or max(p[i:i+k+1])!=p[i+k]:ct+=1
print(ct)

Submission status: Wrong Answer

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

A = list(map(int,input().split()))
ans = n-k+1
for i in range(n-k+1):
  new = A[i:i+k+1]
  print(new[0])
  print(min(new))

Submission status: Wrong Answer

Solution code:
def InputToInt():
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A
    
if __name__ == '__main__':
    N, K = InputToInt()
    P = InputToInt()
    c = 1
    for i in range(N-K):
        if P[i] > P[i+1] or P[i+K-1] > P[i+K]:
            c += 1
    print(c)

Submission status: Wrong Answer

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

sorted_p = []

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

seen = []
[x for x in sorted_p if x not in seen and not seen.append(x)]

print(len(seen))

Submission status: Wrong Answer

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

cnt = 0
for i in range(n - k):
  first = [x - y for (x, y) in zip(p[i:i + k], sorted(p[i:i + k])) ]
  second = [a - b for (a, b) in zip(p[i + 1 : i + 1 + k], sorted(p[i + 1 : i + 1 + k])) ]
  print(first, second)
  if first != second:
    cnt += 1
    
if cnt == 0:
  print(1)
else:
  print(cnt)

Submission status: Wrong Answer

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

ans = n - k + 1

s = list(map(int, input().split()))


for i in range(n - k):
    a = s[i:i + k]
    if a[0] == min(a) and s[i + k] > max(a):
        ans -= 1

b = []
prev = s[0]

c = 1
nc = -1

for i in s[1:]:
    if prev > i:
        c = 1
    else:
        c += 1
        if c >= k:
            nc += 1
    prev = i

if nc > 0:
    ans -= nc

print(ans)

Submission status: Wrong Answer

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

for i in range(N - K + 1):
  target = P[i:i+K]
  print(target)
  target.sort()
  new_list = P[:i] + target + P[i+K:]
  res_set.add(''.join(new_list))

print(len(res_set))

Submission status: Wrong Answer

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

arr  = list(map(int,input().split()))

if n == k :
  print(1)
else :
  print(n-k)

Submission status: Wrong Answer

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

lst = []

for i in range(N-K+1):
    l = sorted(P[i:i+K]) + P[K:]
    l = "".join([str(t) for t in l])
    lst.append(l)

set(lst)
print(len(lst)-1)

Submission status: Wrong Answer

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

count = 1
for i in range(1,N-K+1):
  if P[i]-P[i-1]<0 or P[K+i-1]-P[K+i-1-1]<0:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
p = [int(i) for i in input().split()]
up = []
for i in range(n-1):
  if p[i+1]>p[i]:
    up.append(i)
    
d = [up[i+1]-up[i] for i in range(len(up)-1)]
c = d.count(k-1)
ans = n-k+1-c
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = input().split()  

a = N - M + 1

if N == M:
    print("1")
else:
    print(int(a))

Submission status: Wrong Answer

Solution code:
import sys
import heapq
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')

N,k=map(int,input().split())

p=list(map(int,input().split()))
q=[n*(-1) for n in p]
cnt=1

for i in range(N-k-1):
	heapq.heapify(p[i:i+k])
	heapq.heapify(q[i+1:i+k+1])
	if heapq.heappop(p[i:i+k])==p[i] and heapq.heappop(q[i+1:i+k+1])==q[i+k+1]:
		cnt+=0
	else:
		cnt+=1
	
print(cnt)

Submission status: Wrong Answer

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

if n == k:
    print(1)
    exit()

ps = list(map(int, input().split()))

valid = [0] * (n + k+1)
for i in range(n-1):
    if ps[i] > ps[i+1]:
        valid[i] += 1
        valid[i + k] -= 1
for i in range(1, n + k + 1):
    valid[i] += valid[i - 1]
cnt = 0
has_zero = False
for i in range(k, n):
    if valid[i] != 0:
        cnt += 1
    else:
        has_zero = True
if has_zero:
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import math

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

if a.count(k) == 0:
  print(1)
elif a[a.index(k)-1] < a[a.index(k)]:
  print(math.factorial(len(a)-a.index(k)-1))
else:
  print(math.factorial(len(a)-a.index(k)+1))

Submission status: Wrong Answer

Solution code:
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,k = MAP()
p = MAP()
ans=0

for i in range(n-k+1):
    tmp = p[i:i+k]
    if (i-1)>=0:
        if min(tmp)<p[i-1]:
            ans+=1
    if i+k<=n-1:
        if max(tmp)>p[i+k]:
            ans+=1

print(max(1,ans))

Submission status: Wrong Answer

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

sum = 1
for i in range(n-k-1):
	tempArray = array[i:i+k]
	tempmax = max(tempArray)
	tempmin = min(tempArray)
	if tempmax > array[i+k+1] or tempmin < array[i]:
		sum+=1

print(sum)

Submission status: Wrong Answer

Solution code:
NN = 18
MA = [-1] * ((1<<NN+1)-1)
MI = [1<<100] * ((1<<NN+1)-1)
 
def update(a, x):
    i = (1<<NN) - 1 + a
    MI[i] = x
    MA[i] = x
    while True:
        i = (i-1) // 2
        MI[i] = min(MI[2*i+1], MI[2*i+2])
        MA[i] = max(MA[2*i+1], MA[2*i+2])
        if i == 0:
            break
def rangemin(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    mi = 1<<100
    while l < r:
        if l%2:
            mi = min(mi, MI[l-1])
            l += 1
        if r%2:
            r -= 1
            mi = min(mi, MI[r-1])
        l >>= 1
        r >>= 1
    return mi
def rangemax(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    ma = -1
    while l < r:
        if l%2:
            ma = max(ma, MA[l-1])
            l += 1
        if r%2:
            r -= 1
            ma = max(ma, MA[r-1])
        l >>= 1
        r >>= 1
    return ma

N, K = map(int, input().split())
A = [int(a) for a in input().split()]
a = 0
cnt = 0
for i in range(1, N):
    if A[i-1] > A[i]: a = i 
    if i >= K-1 and a <= i - K + 1: cnt += 1

ans = 1 - max(cnt-1, 0)
for i in range(N):
    update(i, A[i])
    if i >= K:
        mi = rangemin(i-K, i)
        ma = rangemax(i-K+1, i+1)
        if mi != A[i-K] or ma != A[i]:
            ans += 1

print(ans)

Submission status: Wrong Answer

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

sum = 1
for i in range(n-k-1):
	maxtemp = max(array[i:i+k])
	if maxtemp > array[i+k+1]:
		sum+=1

print(sum)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(200000)


def fact(x):
    if x <= 1:
        return 1
    else:
        return fact(x - 1) * x


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

cnt = 0
for i in range(1, n):
    if p[i-1] > p[i]:
        cnt += 1

ans = fact(cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
    """ define what you want to do with 0 index, ex) size = tree_size, func = min or max, sta = default_value """
    
    def __init__(self,size,func,sta):
        self.n = size
        self.size = 1 << size.bit_length()
        self.func = func
        self.sta = sta
        self.tree = [sta]*(2*self.size)

    def build(self, list):
        """ set list and update tree"""
        for i,x in enumerate(list,self.size):
            self.tree[i] = x

        for i in range(self.size-1,0,-1):
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    def set(self,i,x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    
    def get(self,l,r):
        """ take the value of [l r) with func (min or max)"""
        l += self.size
        r += self.size
        res = self.sta

        while l < r:
            if l & 1:
                res = self.func(self.tree[l],res)
                l += 1
            if r & 1:
                res = self.func(self.tree[r-1],res)
            l >>= 1
            r >>= 1
        return res

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

segmin = SegTree(n,min,10**18)
segmax = SegTree(n,max,-1)
segmin.build(p)
segmax.build(p)

count = [1]*n
for i in range(1,n):
    if p[i] > p[i-1]:
        count[i] = count[i-1]+1
if n == k or max(count) == n:
    print(1)
    exit()
ans = 1
check = False
if count[k-1] == k:
    check = True
for i in range(k,n):
    if count[i] >= k:
        if check:
            continue
        else:
            check = True
            ans += 1
            continue
    elif segmin.get(i-k,i+1) == p[i-k] and segmax.get(i-k,i+1) == p[i]:
        continue
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegTreeMax():
    def segfunc(self, x, y):
        if x > y:
            return x
        else:
            return y

    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segfunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segfunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segfunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segfunc(res, self.seg[begin])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[begin]), self.seg[end])
        return res

class SegTreeMin():
    def segfunc(self, x, y):
        if x < y:
            return x
        else:
            return y

    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segfunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segfunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segfunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segfunc(res, self.seg[begin])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[begin]), self.seg[end])
        return res

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    csum = [0]*n
    for i in range(1, n):
        csum[i] += csum[i-1]
        if p[i-1] > p[i]:
            csum[i] += 1
    seg_max = SegTreeMax(-float("inf"), p)
    seg_min = SegTreeMin( float("inf"), p)
    ans = 0
    f = True
    for i in range(k-1, n):
        if csum[i-k+1] == csum[i]:
            if f:
                ans += 1
                f = False
        elif k <= i and not(p[i-k] == seg_min.query(i-k, i) and p[i] == seg_max.query(i-k+1, i+1)):
            ans += 1
        elif i == k-1 and csum[i-k+1] < csum[i]:
            ans += 1
        #print(i, ans, p[i-k+1:i+1])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p = [i for i in input().split()]
ans = set()
for i in range(n - k + 1):
    t = ''.join(p[:i]) + ''.join(sorted(p[i:i+k])) + ''.join(p[i+k:])
    ans.add(t)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
# 連続するK要素を選ぶパターン、n-k+1
mink=min(p[:k])
maxk=max(p[:k])
eq=list(range(n-k+1))
for i in range(n-k+1-1):
  if p[i]==mink and p[i+k]>maxk:
    eq[i+1]=eq[i]
    pass
  if p[i]==mink:
    mink=min(p[i+1:i+k+1])
    maxk=max(maxk,p[i+k])
  if p[i]==maxk:
    mink=min(mink,p[i+k])
    maxk=max(p[i+1:i+k+1])
  else:
    mink=min(mink,p[i+k])
    maxk=max(maxk,p[i+k])

pre=p[0]
a=[0]
c=0
for pi in p[1:]:
  if pre<pi:
    c+=1
  else:
    c=0
  pre=pi
  a.append(c)
eqi=-1
for i in range(n-k+1):
  if a[i+k-1]>=k-1:
    if eqi==-1:
      eqi=i
    else:
      eq[i]=eqi

print(len(set(eq)))
#print(eq)
#print(a)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
# 連続するK要素を選ぶパターン、n-k+1
mink=min(p[:k])
maxk=max(p[:k])
eq=list(range(n-k+1))
for i in range(n-k+1-1):
  if p[i]==mink and p[i+k]>maxk:
    eq[i+1]=eq[i]
    pass
  if p[i]==mink:
    mink=min(p[i+1:i+k+1])
    maxk=max(maxk,p[i+k])
  if p[i]==maxk:
    mink=min(mink,p[i+k])
    maxk=max(p[i+1:i+k+1])
  else:
    mink=min(mink,p[i+k])
    maxk=max(maxk,p[i+k])
s=-1
for i in range(n-k+1):
  a=p[i]
  f=True
  for b in p[i+1:i+k]:
    if a<b:
      a=b
      continue
    else:
      f=False
      break
  if f:
    if s==-1:
      s=i
    else:
      eq[i]=s

print(len(set(eq)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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