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:
#!/usr/bin/env python3
#AGC38 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
p = LI()
ans = 0
i = 0
while i < n:
    lst = p[i:i+k]
    tmp = sorted(lst)
    if i + k >= n:
        break
    for j in range(min(k,n-i)):
        if tmp[j] != lst[j]:
            ans += 1
    i += k
if ans == 0:
    print(1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
p_list = list(map(int, input().split()))
pre_num = -1
sort_k = 0
last = 0
for i in range(n):
  if p_list[i] > pre_num:
    last += 1
    if last >= k:
      sort_k += 1
  else:
    last = 1
  pre_num = p_list[i]
if sort_k > 0:
  sort_k -= 1
sort_k1 = 0
for i in range(n - k):
  if min(p_list[i : i + k + 1]) == p_list[i] and max(p_list[i : i + k + 1]) == p_list[i + k]:
    sort_k1 += 1
print(n - k + 1 - sort_k - sort_k1)

Submission status: Wrong Answer

Solution code:
class SparseTableMAX():
    def __init__(self, array, n):
        '''テーブルを構築する'''
        self.row_size = n.bit_length()
        
        # log_tableを構築する
        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1
        
        # sparse_tableを構築する
        self.sparse_table = [[0] * n for _ in range(self.row_size)]
        for i in range(n):
            self.sparse_table[0][i] = array[i]
        for row in range(1, self.row_size):
            for i in range(n - (1 << row) + 1):
               self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \
                                                       self.sparse_table[row - 1][i + (1 << row - 1)])

    def _merge(self, num1, num2):
        '''クエリの内容'''
        return max(num1, num2)

    def query(self, l, r):
        '''区間[l, r)に対するクエリに答える'''
        if r == l:
            return None
        row = self.log_table[r - l]
        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])


class SparseTableMIN():
    def __init__(self, array, n):
        '''テーブルを構築する'''
        self.row_size = n.bit_length()
        
        # log_tableを構築する
        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1
        
        # sparse_tableを構築する
        self.sparse_table = [[0] * n for _ in range(self.row_size)]
        for i in range(n):
            self.sparse_table[0][i] = array[i]
        for row in range(1, self.row_size):
            for i in range(n - (1 << row) + 1):
               self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \
                                                       self.sparse_table[row - 1][i + (1 << row - 1)])

    def _merge(self, num1, num2):
        '''クエリの内容'''
        return min(num1, num2)

    def query(self, l, r):
        '''区間[l, r)に対するクエリに答える'''
        if r == l:
            return None
        row = self.log_table[r - l]
        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])
      
n, k = map(int, input().split())
a = list(map(int, input().split()))
max_st = SparseTableMAX(a, n)
min_st = SparseTableMIN(a, n)
ans = 0
top = [False]*n
las = [False]*n
for i in range(n):
    if i + k > n:
        continue
    l = a[i]
    r = a[i+k-1]
    l_max = max_st.query(i, i+k-1)
    r_min = min_st.query(i+1, i+k)
    if l > r_min:
        top[i] = True
    if l_max > r:
        las[i] = True

for i in range(n):
    if i + k > n:
        if top[i-1]:
            ans += 1
        continue
    if las[i]:
        ans += 1
        continue
    if i-1 > 1 and top[i-1]:
        ans += 1
        continue

    
i = 0
j = 0
while True:
    if j == k-1:
        ans += 1
        break
    if i+j+1 == n:
        break
    if a[i+j] < a[i+j+1]:
        j += 1
    else:
        i = i+j+1
        j = 0
print(ans)

Submission status: Wrong Answer

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

sortList = []
counter = 0
counter2 = 0
number = 0
for i in range(N-K+1):
    if i ==0:
        prev_min = min(P[i:i+K])
        prev_max = max(P[i:i+K])
        prev_num = P[i]
    else:
        if prev_min < min(P[i:i+K]) and prev_max < max(P[i:i+K]):
            counter += 1
        if(prev_num < P[i]):
            number += 1
            if number > K-2:
                counter2 += 1
        else:
            number = 0
            
        prev_min =  min(P[i:i+K]) 
        prev_max =  max(P[i:i+K]) 

if counter2 > 0:
    counter2 -= 1
else:
    counter2 = 0
print(N - K + 1 - counter + counter2)

Submission status: Wrong Answer

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

temp = 0
for i in range(K-1, 0, -1):
    if P[i] >= P[i-1]:
        temp += 1
    else:
        break

if temp > K-1:
    same = 1
else:
    same = 0

ans, M = N-K+1, max(P[:K])

ans, temp, ser = N-K+1, 0, 0
com = [0] * (N-K)
for i in range(N-K):
    if P[i+K] > P[i+K-1]:
        temp += 1
        if temp == K - 1:
            same += 1

        if P[i+K] >= M:
            M = P[i+K]
            com[i] = 1
    else:
        temp = 0

Pr = P[::-1]
m = min(Pr[:K])
for i in range(N-K):
    if Pr[i+K] <= m and com[-i-1] == 1:
        ans -= 1

if same > 0:
    ans -= same - 1
print(ans)

Submission status: Wrong Answer

Solution code:
inp = input().split()
n = int(inp[0])
k = int(inp[1])
ar = list(map(lambda x: int(x), input().split()))
ans = list()

total = 0
i = 0
while i <= n-k:
  o = ar[i:i+k]
  flg = False
  flg2 = False
  for z in range(len(o)-1):
    if o[z] < o[z+1]:
      continue
    
    if flg:
      flg2 = True
      break
    
    poped = o.pop(z)
    jj = -1
    for j in range(len(o)):
      if poped < o[j]:
        jj = j
        break
    if jj > -1:
      o.insert(jj, poped)
    else:
      o.append(poped)
    flg = True
    
  if flg2:
    i += 1
    continue

  p = True
  for x in ans:
    if x == (ar[:i]+o+ar[i+k:]):
      p = False
      break
  if p:
    ans.append(ar[:i]+o+ar[i+k:])
  i += 1

print(len(ans))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
P=[int(i) for i in input().split()]
import collections
from collections import deque
M1,M2=deque(),deque()
A1,A2=[],[]
M1.append(P[0])
for i in range(1,n):
  
  while M1:
    if P[M1[-1]]>P[i]:
      M1.pop()
    else:
      M1.append(i)
      break
  if not M1:
    M1.append(i)
  if M1[0]==i-k-1:
    M1.popleft()
  A1.append(P[M1[0]])
M2.append(P[0])
for i in range(1,n):
  
  while M2:
    if P[M2[-1]]<P[i]:
      M2.pop()
    else:
      M2.append(i)
      break
  if not M2:
    M2.append(i)
  if M2[0]==i-k-1:
    M2.popleft()
  A2.append(P[M2[0]])
ans=1
for i in range(n-k):
  if A1[i+k-2]==P[i] and A2[i+k-2]==P[i+k]:
    continue
  else:
    ans+=1
Q=[0]*n
for i in range(1,n):
  if P[i]>P[i-1]:
    Q[i]=Q[i-1]+1
  else:
    continue
count=0
for i in range(n):
  if Q[i]>=k-1:
    count+=1
print(ans-max(0,count-1))

Submission status: Wrong Answer

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

result = N - K + 1
 
for i in range(1, N - K + 1):
  pre = P[i - 1]
  sub = P[i:i+K]
  if P[i + K - 1] == max(sub) and pre < min(sub):
    result = result - 1

print(result)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p1=[int(i) for i in input().split()]
p2=[0]*(n-1)
j=1
for i in range(n-1):
    if p1[i]>p1[i+1]:
        p2[i]=j
        j+=1
#print(p2)
x=p2[:k-1]
s1=sum(x)
p3="".join(map(str,p2))
j=0

for i in range(n-k):
    s2=s1-p2[i]+p2[i+k-1]
    if s1!=s2 and (s1!=0 or s2!=0):
        j+=1
        #print(i)
    s1=s2
print(j)

Submission status: Wrong Answer

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

ind = []

for i in range(N-1):
    if P[i] > P[i+1]:
        ind.append(i+1)
    else:
        continue

cnt = 0
old_B = {}

for i in range(N-K+1):
    A = range(i, i+K)
    B = set(ind) & set(A)
    if B == {}:
        continue
    elif B != old_B:
        cnt += 1
    else:
        continue
    old_B = B

print(cnt)

Submission status: Wrong Answer

Solution code:
class Min_seg:
    def __init__(self,n,init_val,ide_ele = 10**9):
        # set_val
        self.ide_ele = ide_ele #単位元
        self.n = n #要素数
        self.num = 2 ** (self.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]
            # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = min(self.seg[2 * i + 1], self.seg[2 * i + 2])
    def update(self,k, x):
        k += self.num - 1
        self.seg[k] = x
        while k + 1:
            k = (k - 1) // 2
            self.seg[k] = min(self.seg[k * 2 + 1], self.seg[k * 2 + 2])


    def query(self,p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = min(res, self.seg[p])
            if q & 1 == 1:
                res = min(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = min(res, self.seg[p])
        else:
            res = min(min(res, self.seg[p]), self.seg[q])
        return res

class Max_seg:
    def __init__(self,n,init_val,ide_ele = 0):
        # set_val
        self.ide_ele = ide_ele #単位元
        self.n = n #要素数
        self.num = 2 ** (self.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]
            # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = max(self.seg[2 * i + 1], self.seg[2 * i + 2])
    def update(self,k, x):
        k += self.num - 1
        self.seg[k] = x
        while k + 1:
            k = (k - 1) // 2
            self.seg[k] = max(self.seg[k * 2 + 1], self.seg[k * 2 + 2])


    def query(self,p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = max(res, self.seg[p])
            if q & 1 == 1:
                res = max(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = max(res, self.seg[p])
        else:
            res = max(max(res, self.seg[p]), self.seg[q])
        return res

n,k = map(int,input().split())
p = list(map(int,input().split()))
seg1 = Min_seg(n,p)
seg2 = Max_seg(n,p)

ans = n-k+1
for i in range(n-k):
    #print(0,p[i],seg1.query(i,i+k-1))
    #print(1,p[i+k],seg2.query(i+1,i+k+1))
    if p[i] == seg1.query(i,i+k-1) and p[i+k] == seg2.query(i+1,i+k+1):
        ans -= 1

#print(ans,"試し")

d = [0 for _ in range(n-1)]
for i in range(n-1):
    if p[i] < p[i+1]:
        d[i] = 1

seg3 = Min_seg(n-1,d)
data = [seg3.query(i,i+k-1) for i in range(n-k+1)]
#print(data)


if k > 2 and sum(data) >= 1:
    now = -1
    for i in range(n-k+1):
        if data[i] == 1:
            if i == 0:now += 1
            elif data[i-1] == 0:now += 1
    ans -= now

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

n, k = map(int, input().split())
p = list(map(int, input().split()))
count = 0
a = p[0:k]

h1 = []
h2 = []
for i in range(len(a)):
    heapq.heappush(h1, a[i])
    heapq.heappush(h2, -a[i])
    

for i in range(k,n):
    heapq.heappush(h1, p[i])
    heapq.heappush(h2, -p[i])
    
    if p[i]>=(-h2[0]) and h1[0] == p[i-k]:
        count += 1
    if h1[0] == p[i-k]:
        heapq.heappop(h1)
        
print(n-k+1-count)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
P=[int(i) for i in input().split()]
import collections
from collections import deque
M1,M2=deque(),deque()
A1,A2=[],[]
M1.append(P[0])
for i in range(1,n):
  
  while M1:
    if P[M1[-1]]>P[i]:
      M1.pop()
    else:
      M1.append(i)
      break
  if not M1:
    M1.append(i)
  if M1[0]==i-k-1:
    M1.popleft()
  A1.append(P[M1[0]])
M2.append(P[0])
for i in range(1,n):
  
  while M2:
    if P[M2[-1]]<P[i]:
      M2.pop()
    else:
      M2.append(i)
      break
  if not M2:
    M2.append(i)
  if M2[0]==i-k-1:
    M2.popleft()
  A2.append(P[M2[0]])
ans=1
for i in range(n-k):
  if A1[i+k-2]==P[i] and A2[i+k-2]==P[i+k]:
    continue
  else:
    ans+=1
  print(ans)
Q=[0]*n
for i in range(1,n):
  if P[i]>P[i-1]:
    Q[i]=Q[i-1]+1
  else:
    continue
count=0
for i in range(n):
  if Q[i]>=k-1:
    count+=1
print(ans-max(0,count-1))

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 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]:
    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:
from sys import stdin
import bisect

N, K = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]

ans = 1
Q = P[:K]
Q.sort(reverse=True)

for i in range(N - K):
    if P[i] != Q[-1] or Q[0] > P[i + K]:
        ans += 1
    if P[i] == Q[-1]:
        Q.pop()
    bisect.insort_left(Q, P[i + K])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

#+++++
		
def main():
	n,k = map(int, input().split())
	al = list(map(int, input().split())	)
	
	b=[0]*n
	for i,(cc,nn) in enumerate(zip(al,al[1:])):
		if cc <= nn:
			b[i]=1
	kk=0
	ans=n-k+1
	aaa=-1
	for v in b:
		if v == 0:
			kk=1
		else:
			kk+=1
			if kk > k-1:
				aaa+=1
	ans=min(ans,ans-aaa)
		
	
	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p1=[int(i) for i in input().split()]
p2=[0]*(n-1)
j=1
for i in range(n-1):
    if p1[i]>p1[i+1]:
        p2[i]=j
        j+=1
#print(p2)
x=p2[:k-1]
s1=sum(x)
p3="".join(map(str,p2))
if "0"*(k-1) in p3:
    j=1
else:
    j=0
for i in range(n-k):
    s2=s1-p2[i]+p2[i+k-1]
    if s1!=s2 and (s1!=0 or s2!=0):
        j+=1
        #print(i)
    s1=s2
print(j)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
sortList = []
counter = 0
number = 0
for i in range(N-K+1):
    if i ==0:
        prev_min = min(P[i:i+K])
        prev_max = max(P[i:i+K])
        prev_num = P[i]
    else:
        if prev_min < min(P[i:i+K]) and prev_max < max(P[i:i+K]):
            counter += 1
        if(prev_num < P[i]):
            number += 1
            if number > K-2:
                counter += 1
        else:
            number = 0
            
        prev_min =  min(P[i:i+K]) 
        prev_max =  max(P[i:i+K]) 

print(N - K + 1 - counter + 1)

Submission status: Wrong Answer

Solution code:
n,k =map(int,input().split())
p = list(map(int,input().split())) + [n]
q = p
r = p

def segfunc(x,y):
    return min(x,y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele = -1
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
init(q)

def segfunc1(x,y):
    return max(x,y)

def init1(init_val):
    #set_val
    for i in range(n):
        seg1[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg1[i]=segfunc1(seg1[2*i+1],seg1[2*i+2]) 
    
def query1(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc1(res,seg1[p])
        if q&1 == 1:
            res = segfunc1(res,seg1[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc1(res,seg1[p])
    else:
        res = segfunc1(segfunc1(res,seg1[p]),seg1[q])
    return res

#####単位元######
ide_ele = -1
#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg1=[ide_ele]*2*num
init(r)


ans = 1
if p[0:k] != sorted(p[0:k]):
    ans += 1

for i in range(1,len(p)-k-2):
    if not (p[i-1] < query(i,i+k) and query1(i,i+k) < p[i+k]):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n, k =map(int, input().split())
P = list(map(int, input().split()))
ans = n-k+1
m = 0
for i in range(k,n):
  if max(P[i-k+1:i+1]) == P[i] and min(P[i-k:i]) == P[i-k]:
    ans -= 1
for i in range(k,n+1):
  if sorted(P[i-k:i]) == P[i-k:i]:
    m += 1
if m == 0:
  print(ans)
else:
  print(ans-m + 1)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
cnt = 1
flag = False
for i in range(N-K+1):
  if i == 0:
    pass
  else:
    #print(i,sorted(P[i-1:i+K-1])[1:] + [P[i+K-1]],P[i:i+K])
    if sorted(P[i:i+K])==P[i:i+K] and flag == False:
      flag = True
      cnt += 1  
    elif sorted(P[i:i+K])!=P[i:i+K] and sorted(P[i-1:i+K-1])[1:]+[P[i+K-1]] !=sorted(P[i:i+K]):
      cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n, k = [int(v) for v in input().split()]
p_s = [int(v) for v in input().split()]

ans = 1
for i in range(1, n - k):
  p_ki = p_s[i:i+k]
  max_p = max(p_ki)
  min_p = min(p_ki)
  ans += 1
  if min_p == p_s[i - 1] and max_p == p_s[i+k-1]:
    ans -=1

print(ans)

Submission status: Wrong Answer

Solution code:
class SparseTableMAX():
    def __init__(self, array, n):
        '''テーブルを構築する'''
        self.row_size = n.bit_length()
        
        # log_tableを構築する
        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1
        
        # sparse_tableを構築する
        self.sparse_table = [[0] * n for _ in range(self.row_size)]
        for i in range(n):
            self.sparse_table[0][i] = array[i]
        for row in range(1, self.row_size):
            for i in range(n - (1 << row) + 1):
               self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \
                                                       self.sparse_table[row - 1][i + (1 << row - 1)])

    def _merge(self, num1, num2):
        '''クエリの内容'''
        return max(num1, num2)

    def query(self, l, r):
        '''区間[l, r)に対するクエリに答える'''
        if r == l:
            return None
        row = self.log_table[r - l]
        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])


class SparseTableMIN():
    def __init__(self, array, n):
        '''テーブルを構築する'''
        self.row_size = n.bit_length()
        
        # log_tableを構築する
        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1
        
        # sparse_tableを構築する
        self.sparse_table = [[0] * n for _ in range(self.row_size)]
        for i in range(n):
            self.sparse_table[0][i] = array[i]
        for row in range(1, self.row_size):
            for i in range(n - (1 << row) + 1):
               self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \
                                                       self.sparse_table[row - 1][i + (1 << row - 1)])

    def _merge(self, num1, num2):
        '''クエリの内容'''
        return min(num1, num2)

    def query(self, l, r):
        '''区間[l, r)に対するクエリに答える'''
        if r == l:
            return None
        row = self.log_table[r - l]
        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])
      
n, k = map(int, input().split())
a = list(map(int, input().split()))
max_st = SparseTableMAX(a, n)
min_st = SparseTableMIN(a, n)
ans = 0
top = [False]*n
las = [False]*n
for i in range(n):
    if i + k > n:
        continue
    l = a[i]
    r = a[i+k-1]
    l_max = max_st.query(i, i+k-1)
    r_min = min_st.query(i+1, i+k)
    if l > r_min:
        top[i] = True
    if l_max > r:
        las[i] = True

for i in range(n):
    if i + k > n:
        continue
    if las[i]:
        ans += 1
        continue
    if i-1 > 1 and top[i-1]:
        ans += 1
        continue
if top[i-1]:
    ans += 1
    
i = 0
j = 0
while True:
    if j == k-1:
        ans += 1
        break
    if i+j+1 == n:
        break
    if a[i+j] < a[i+j+1]:
        j += 1
    else:
        i = i+j+1
        j = 0
print(ans)

Submission status: Wrong Answer

Solution code:
n, k =map(int, input().split())
P = list(map(int, input().split()))
ans = n-k+1
m = 0
for i in range(k,n):
  if max(P[i-k+1:i+1]) == P[i] and min(P[i-k:i]) == P[i-k]:
    ans -= 1
for i in range(k,n+1):
  print(P[i-k:i])
  print(sorted(P[i-k:i]))
  if sorted(P[i-k:i]) == P[i-k:i]:
    m += 1
if m == 0:
  print(ans)
else:
  print(ans-m + 1)

Submission status: Wrong Answer

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
import heapq
N, K = map(int, input().split())
P = list(map(int, input().split()))
heapq.heapify(P)
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 tmp[0] <= min(tmp) and P[i + K] >= max(tmp):
                ans -= 1
if flag != N - K + 1:
    ans += 1
print(str(ans))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import bisect

N, K = [int(x) for x in stdin.readline().rstrip().split()]
P = stdin.readline().rstrip().split()

ans = 1
Q = P[:K]
Q.sort(reverse=True)

for i in range(N - K):
    if P[i] != Q[-1] or Q[0] > P[i + K]:
        ans += 1
    if P[i] == Q[-1]:
        Q.pop()
    if Q[0] <= P[i + K]:
        bisect.insort_left(Q, P[i + K])

print(ans)

Submission status: Wrong Answer

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)
        diff = ''
        for i in range(N):
            if P.pop() != sorted_p.pop():
                diff += '1'
            else:
                diff += '0'
        ans = 0
        print(1)
        # 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: Wrong Answer

Solution code:
class SparseTableMAX():
    def __init__(self, array, n):
        '''テーブルを構築する'''
        self.row_size = n.bit_length()
        
        # log_tableを構築する
        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1
        
        # sparse_tableを構築する
        self.sparse_table = [[0] * n for _ in range(self.row_size)]
        for i in range(n):
            self.sparse_table[0][i] = array[i]
        for row in range(1, self.row_size):
            for i in range(n - (1 << row) + 1):
               self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \
                                                       self.sparse_table[row - 1][i + (1 << row - 1)])

    def _merge(self, num1, num2):
        '''クエリの内容'''
        return max(num1, num2)

    def query(self, l, r):
        '''区間[l, r)に対するクエリに答える'''
        if r == l:
            return None
        row = self.log_table[r - l]
        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])


class SparseTableMIN():
    def __init__(self, array, n):
        '''テーブルを構築する'''
        self.row_size = n.bit_length()
        
        # log_tableを構築する
        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1
        
        # sparse_tableを構築する
        self.sparse_table = [[0] * n for _ in range(self.row_size)]
        for i in range(n):
            self.sparse_table[0][i] = array[i]
        for row in range(1, self.row_size):
            for i in range(n - (1 << row) + 1):
               self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \
                                                       self.sparse_table[row - 1][i + (1 << row - 1)])

    def _merge(self, num1, num2):
        '''クエリの内容'''
        return min(num1, num2)

    def query(self, l, r):
        '''区間[l, r)に対するクエリに答える'''
        if r == l:
            return None
        row = self.log_table[r - l]
        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])
      
n, k = map(int, input().split())
a = list(map(int, input().split()))
max_st = SparseTableMAX(a, n)
min_st = SparseTableMIN(a, n)
ans = 0
top = [False]*n
las = [False]*n
for i in range(n):
    if i + k > n:
        continue
    l = a[i]
    r = a[i+k-1]
    l_max = max_st.query(i, i+k-1)
    r_min = min_st.query(i+1, i+k)
    if l > r_min:
        top[i] = True
    if l_max > r:
        las[i] = True

for i in range(n):
    if i + k > n:
        continue
    if las[i]:
        ans += 1
        continue
    if i-1 > 1 and top[i-1]:
        ans += 1
        continue
i = 0
j = 0
while True:
    if j == k-1:
        ans += 1
        break
    if i+j+1 == n:
        break
    if a[i+j] < a[i+j+1]:
        j += 1
    else:
        i = i+j+1
        j = 0
print(ans)

Submission status: Wrong Answer

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

L = [0 for i in range(N-1)]
temp = P[0]
for i in range(1,N):
    if temp > P[i]:
        L[i-1] = 1
    temp = P[i]
    
cnt = 0
    
for i in range(N-1):
    if L[i] == 1:
        chk = 0
        for j in range(1,K):
            if 0 <= i-j and i+j < N-1:
                if L[i+j] == L[i-j]:
                    chk += 1
                else:
                    break
        if chk == K-2:
            cnt += 1
            
zero = []
z = 0
for i in range(N-1):
    if L[i] == 0:
        z += 1
    else:
        zero.append(z)
        z = 0

cnt2 = 0
for i in range(len(zero)):
    if zero[i] >= K-1:
        cnt2 += zero[i]-K+2
        
print(N-K+1-cnt-cnt2)

Submission status: Wrong Answer

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(np.unique(box))
  print(len(np.unique(box)))
else:
  print(1)

Submission status: Wrong Answer

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

if k == n:
    print('1')
    exit()
ans = 1
irekawaranai = 0

minl = [0]*(n-k+1)
maxl = [0]*(n-k+1)
tmpmin = min(p[:k])
tmpmax = max(p[:k])
for i in range(k, n):
    minl[i-k] = tmpmin
    maxl[i-k] = tmpmax
    if p[i] > tmpmax:
        tmpmax = p[i]
    elif p[i] < tmpmin:
        tmpmin = p[i]
    if p[i-k] == tmpmax:
        tmpmax = max(p[i-k+1:i+1])
    elif p[i-k] == tmpmin:
        tmpmin = min(p[i-k+1:i+1])



for i in range(n-k):
    if p[i] == minl[i] and maxl[i] < p[i+k]:
      	pass
    elif p[i+1] == minl[i] and maxl[i] < p[i+k]:
        irekawaranai += 1
    else:
        ans += 1
if irekawaranai > 0:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
n,k = map(int,input().split())
p = [int(i) for i in input().split()]
ll = p[0:k]

ll.sort()
c_list = ll[1:]
p.pop(0)
#print(c_list,p)                                                               
roop = n-k
count = n+1-k
f = 0
for i in range(roop):
    list = p[i:k+i]
    list_copy = copy.copy(list)
    list.sort()
    if list == list_copy:
        count -= 1
        f = 1
#        print(list)                                                           
        continue
#    print(c_list,list)                                                        
    if c_list == list[0:k-1]:
#        print(c_list)                                                         
        count -= 1
    c_list = list[1:]

print(count+f)

Submission status: Wrong Answer

Solution code:
import numpy as np

n,k = map(int, input().split())
p_list = np.array(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] = temp.min
    maxs[i] = temp.max

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)