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:
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 = [-1] + list(map(int, input().split())) + [n+1]
n = n+2
max_st = SparseTableMAX(a, n)
min_st = SparseTableMIN(a, n)
ans = 0

for i in range(n):
    if i + k >= n:
        continue
    l = a[i]
    r = a[i+k]
    min_ = min_st.query(i, i+k)    
    max_ = max_st.query(i+1, i+k+1)
    if l != min_ or r != max_:
        ans += 1
if a == sorted(a):
    ans += 1
print(ans)

Submission status: Wrong Answer

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

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

if no_change:
    for j in range(k-1):
        if p[-k+j] > q[-k+j+1]:
            break
    else:
        ans -= 1
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
seq=1

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

print(count)

Submission status: 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])
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:
        m = Pr[i+K]
        if com[-i-1] == 1:
            ans -= 1

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

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 = True
else:
    same = False

ans, M = N-K+1, max(P[:K])
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:
        m = Pr[i+K]
        if com[-i-1] == 1:
            ans -= 1

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

Submission status: Wrong Answer

Solution code:
def input():return next(input_sample)
input_sample=iter("""
5 3
0 2 1 4 3
""".split("\n")[1:-1])

#問題を解く
def main():

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

if __name__ == '__main__':
	main()

Submission status: 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
seq=1

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

print(count)

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 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:
d = input().split(' ')
N = int(d[0])
K = int(d[1])
d = input().split(' ')
P = [int(i) for i in d]

b_start_p = -2
b_end_p = -2
sum = 0
hf = 0
max = -1

for i in range(N - K + 1):
  a=[]
  
  if max > P[i + K - 1] or b_start_p <= 0:
    for j in range(K):
      a.append(P[i + j])
    new_a = sorted(a)
    fl = 0
    before = 0
    start_p = -2
    end_p = -2
    for j in range(K):
      if new_a[j] != a[j] and fl == 0:
        start_p = j
        fl = 1
        before = 1
      elif new_a[j] == a[j] and before == 1:
        end_p = j
      
    if start_p != -2 and end_p == -2:
      end_p = j

    if start_p  != b_start_p - 1 or end_p != b_end_p:
      if start_p == -2 and end_p == -2 and hf == 0:
        sum = sum + 1
        hf = 1
      elif start_p != -2 or end_p != -2:
        sum = sum + 1

    b_start_p = start_p
    b_end_p = end_p
    max = new_a[K - 1]
    
  else:
    b_start_p = b_start_p - 1
    b_end_p = b_end_p - 1
    max = P[i + K - 1]
  
print(sum)

Submission status: Wrong Answer

Solution code:

n, k = map(int,input().split())
p_list = list(map(int,input().split()))
counter = 1
for i in range(n-k):
    if ((p_list[i] < min(p_list[i+1:i+k])) and (p_list[i+k] > max(p_list[i+1:i+k]))) or p_list[i:i+k] == sorted(p_list[i:i+k]):
        counter += 0
    else:
        counter += 1

print(counter)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
p_list = list(map(int, input().split()))
initial_number = N-K+1
count_1 = 0
count_2 = 0
for i in range(initial_number-1):
    p_range = p_list[i:i+K+1]
    p_range_asc = sorted(p_range)
    if min(p_range_asc) == p_range[0] and max(p_range_asc) == p_range[-1]:
        count_1 += 1
for i in range(initial_number):
    p_range_2 = p_list[i:i+K]
    p_range_asc_2 = sorted(p_range_2)
    if p_range_2 == p_range_asc_2:
        count_2 += 1
        
if count_2 >= 1:
    count_2 -=1
output = initial_number - (count_1 + count_2) 
print(output)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
p_list = list(map(int, input().split()))
initial_number = N-K+1
count_1 = 0
count_2 = 0
for i in range(initial_number):
    p_range_2 = p_list[i:i+K]
    p_range_asc_2 = sorted(p_range_2)
    if p_range_2 == p_range_asc_2:
        count_2 += 1
    p_range = p_list[i:i+K+1]
    p_range_asc = sorted(p_range)
    if min(p_range_asc) == p_range[0] and max(p_range_asc) == p_range[-1]:
        count_1 += 1
if len(p_list) == K:
    initial_number += 1
if count_2 >= 1:
    count_2 -=1
output = initial_number - (count_1 + count_2) 
print(output)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
min_, max_ = min(p[:k]), max(p[:k])
ans = n-k+1
for i in range(n-k):
    if p[i] == min_ and p[i+k] > max_:
        ans -= 1
    min_ = min(p[i+k], min_)
    max_ = max(p[i+k], max_)
span = []
count = 1
for i in range(n-1):
    if p[i] < p[i+1]:
        count += 1
    else: 
        if count >= k: span.append(count)
        count = 1
    if i == n-2 and count >= k: span.append(count)
for i in range(len(span)-1):
    for j in range(i+1,len(span)):
        ans -= (span[i]-k+1)*(span[j]-k+1)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
L = LI()



min_l = [0] * n
max_l = [0] * n


min_ret = max_ret = L[0]
for i in range(n):
    min_ret = min(min_ret, L[i])
    max_ret = max(max_ret, L[i])
    min_l[i] = min_ret
    max_l[i] = max_ret



cnt = 1
for i in range(n - k):
    if min_l[i] == L[i] and max_l[i + k] == L[i + k]:
        continue
    else:
        cnt += 1



print(cnt)

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(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()
  if i<k:
    continue
  else:
    A1.append(P[M1[0]])
M2.append(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()
  if i<k:
    continue
  else:
    A2.append(P[M2[0]])
ans=1
for i in range(n-k):
  if A1[i]==P[i] and A2[i]==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 = map(int,input().split())
p_list = list(map(int, input().split()))
initial_number = N-K+1
count_1 = 0
count_2 = 0
for i in range(initial_number):
    p_range = p_list[i:i+K+1]
    p_range_asc = sorted(p_range)
    if min(p_range_asc) == p_range[0] and max(p_range_asc) == p_range[-1]:
        count_1 += 1
    p_range_2 = p_list[i:i+K]
    p_range_asc_2 = sorted(p_range)
    if p_range_2 == p_range_asc_2:
        count_2 += 1
if len(p_list) == K:
    initial_number += 1
if count_2 >= 1:
    count_2 -=1
output = initial_number - (count_1 + count_2) 
print(output)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def check_same_origin(l):
    so_flag = True
    for j in range(k - 1):
        if p[l + j] > p[l + j + 1]:
            so_flag = False
            break
    if so_flag:
        return True
    else:
        return False


n, k = map(int, input().split())
p = list(map(int, input().split()))
result = n - k +1
same_origin = 0
for i in range(n - k):
    if (p[i]<min(p[i+1:i+k])) & (max(p[i+1:i+k])<p[i+k]):
        result -= 1
    if check_same_origin(i):
        same_origin += 1
if check_same_origin(n-k):
    same_origin += 1

if same_origin > 1:
    print(result-same_origin+1)
else:
    print(result)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapreplace


def p_b():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    Hmax = []
    Hmin = []
    for i in range(K):
        heappush(Hmin, P[i])
        heappush(Hmax, -P[i])

    ans = 0
    for i in range(K, N):
        # print(heapreplace(Hmin, P[i]), -heapreplace(Hmax, -P[i]))
        if P[i - K] != heapreplace(Hmin, P[i]) or P[i] != -heapreplace(Hmax, -P[i]):
            ans += 1

    print(ans)


if __name__ == '__main__':
    p_b()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import copy

input = sys.stdin.readline

N, K = map(int, input().split())
P = list(map(int, input().split(' ')))
F = 0  # From
#print(P)
patterns = 0
prevtmp = None
prevhq = None
NTD = False
isNeedSort = False
isDiff = False
while N >= F + K:
    tmp = (P[F:F + K])
#    print(tmp)

    # 優先度付きキューに変換
    hq = copy.copy(tmp)
    heapq.heapify(hq)

    isNeedSort = False
    isDiff = False
    for i in range(len(tmp)):
        hq_item = heapq.heappop(hq)
#        print("hq:{0}, tmp:{1},prev_hq:{2}, prev_tmp:{3}".format(hq_item, tmp[i],prevhq,prevtmp))
        if tmp[i] != hq_item:
            isDiff = True
#            print("detected!")

            if not((tmp[i] == prevtmp and hq_item == prevhq) or (tmp[i] == prevhq and hq_item == prevtmp)):
                isNeedSort = True
#                print("isNeedSort is true")

            prevtmp = tmp[i]
            prevhq = hq_item

        if i == len(tmp) - 1 and not isDiff:
            NTD = True

    if isNeedSort:
        patterns += 1
#        print("count up")

    F += 1

if NTD:
    # 並び替えたけど何も変わらなかったパターンがあれば
#    print("count up omake")
    patterns += 1

#print("パターン数:{}".format(patterns))
print(patterns)

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()
  if i<k:
    continue
  else:
    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()
  if i<k:
    continue
  else:
    A2.append(P[M2[0]])
ans=1
for i in range(n-k):
  if A1[i]==P[i] and A2[i]==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 = map(int, input().split())
p = list(map(int, input().split()))

point = [0] * n
for i in range(n):
    point[p[i]] = i
result = 0
ascend = 0
notA = False
for i in range(k-1):
    if p[i] > p[i+1]:
        notA = True
        break
if notA == False:
    ascend+=1
else:
    result+=1
for i in range(n-k):
    maxp = p[i+k]
    minp = p[i]
    bf = False
    notA = False
    for j in range(i, i+k):
        if p[j] < minp:
            if notA :
                break
            bf = True
        if p[j] > maxp:
            if notA :
                break
            bf = True
        if j != i and p[j] > p[j+1]:
            notA = True
            if bf:
                break
    if notA and bf:
        result+=1
    if notA == False and ascend == 0 and bf:
        ascend += 1

print(result + ascend)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
p_list = list(map(int, input().split()))
initial_number = N-K+1
count_1 = 0
count_2 = 0
for i in range(initial_number):
    p_range = p_list[i:i+K+1]
    p_range_asc = sorted(p_range)
    if p_range[0] == p_range_asc[0] and p_range[-1] == p_range_asc[-1]:
        count_1 += 1
    p_range_2 = p_list[i:i+K]
    p_range_asc_2 = sorted(p_range)
    if p_range_2 == p_range_asc_2:
        count_2 += 1
            
if count_2 >= 1:
    count_2 -=1
output = initial_number - (count_1 + count_2) 
print(output)

Submission status: Wrong Answer

Solution code:
d = input().split(' ')
N = int(d[0])
K = int(d[1])
d = input().split(' ')
P = [int(i) for i in d]

b_start_p = -2
b_end_p = -2
sum = 0
hf = 0

for i in range(N - K + 1):
  a=[]
  for j in range(K):
  	a.append(P[i + j])
    
  new_a = sorted(a)
  
  fl = 0
  before = 0
  start_p = -2
  end_p = -2
  for j in range(K):
    if new_a[j] != a[j] and fl == 0:
      start_p = j
      fl = 1
      before = 1
    elif new_a[j] == a[j] and before == 1:
      end_p = j
      
  if start_p != -2 and end_p == -2:
    end_p = j
      
  if start_p  != b_start_p - 1 or end_p != b_end_p:
    if start_p == -2 and end_p == -2 and hf == 0:
      sum = sum + 1
      hf = 1
    elif start_p != -2 or end_p != -2:
      sum = sum + 1
      
  b_start_p = start_p
  b_end_p = end_p
  
print(sum)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class SegmentTree(object):

    def __init__(self, init_array, seg_func=min, seg_func_null=10 ** 9 + 7):

        self.seg_func = seg_func
        self.seg_func_null = seg_func_null
        self.n = 1
        while self.n < len(init_array):
            self.n *= 2
        self.dat = [0] * (2 * self.n - 1)
        for i in range(len(init_array)):
            self.dat[self.n - 1 + i] = init_array[i]
        for i in range(self.n - 2, -1, -1):
            self.dat[i] = self.seg_func(self.dat[2 * i + 1], self.dat[2 * i + 2])

    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.seg_func(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, p, q):
        # [p, q)
        if q <= p:
            return self.seg_func_null

        p += self.n - 1
        q += self.n - 2
        res = self.seg_func_null

        while q - p > 1:
            if p & 1 == 0:
                res = self.seg_func(res, self.dat[p])
            if q & 1 == 1:
                res = self.seg_func(res, self.dat[q])
                q -= 1
            p = p // 2
            q = (q-1) // 2
        if p == q:
            res = self.seg_func(res, self.dat[p])
        else:
            res = self.seg_func(self.seg_func(res, self.dat[p]), self.dat[q])

        return res


def solve_b(n, k, p_list):

    min_tree = SegmentTree(p_list)
    max_tree = SegmentTree(p_list, max, -1)

    min_list = [0] * n
    max_list = [0] * n

    for i in range(n - k):
        if p_list[i] == min_tree.query(i, i + k + 1):
            min_list[i] = 1

    for i in range(n - k):
        if p_list[i + k - 1] == max_tree.query(i, i + k + 1):
            max_list[i + k] = 1

    res = 1
    # print(min_list, max_list)

    for i in range(n - k):
        if min_list[i] == 0 or max_list[i + k] == 0:
            res += 1

    # count invariant
    straight = 1
    count_k = 0
    for i in range(n - 1):
        if p_list[i] < p_list[i + 1]:
            straight += 1
        else:
            straight = 1
        if straight == k:
            count_k += 1

    if count_k > 0:
        res -= count_k - 1

    return res


def solve_b_greedy(n, k, p_list):

    count_dict = dict()

    for i in range(n - k + 1):
        p_list_new = p_list[:i] + list(sorted(p_list[i:i + k])) + p_list[i + k:]
        p_list_new_hash = ".".join([str(p) for p in p_list_new])
        if p_list_new_hash in count_dict.keys():
            print(i, p_list_new_hash)
        count_dict[p_list_new_hash] = 1

    return len(count_dict)


def main_greed():
    n, k = map(int, input().split())
    p_list = list(map(int, input().split()))
    res = solve_b_greedy(n, k, p_list)
    print(res)


def main():
    n, k = map(int, input().split())
    p_list = list(map(int, input().split()))
    res = solve_b(n, k, p_list)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import heapq

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

Z = [0 for i in range(N)]
tmp = P[0]
count = 1
order = [0 for i in range(N)]
for i in range(1, N):
    if tmp < P[i]:
        count += 1
        if count >= K:
            order[i] = 1
    else:
        count = 1
    tmp = P[i]

print(order)

hp = []
hm = []
heapq.heapify(hp)
heapq.heapify(hm)
used = [0 for i in range(N)]

for i in range(K):
    heapq.heappush(hp, P[i]) # 最小
    heapq.heappush(hm, -P[i]) # 最大

ans = 1
kaburi = [0 for i in range(N)]

for i in range(K, N):
    while used[hp[0]-1] == 1:
        heapq.heappop(hp)
    while used[-hm[0]-1] == 1:
        heapq.heappop(hm)

    if hp[0] == P[i-K] and -hm[0] < P[i]:
        kaburi[i] = 1
        pass
    else:
        ans += 1
    
    used[P[i-K]-1] = 1

    heapq.heappush(hp, P[i])
    heapq.heappush(hm, -P[i])

order_count = 0
for i in range(N):
    if kaburi[i] == 0 and order[i] == 1:
        order_count += 1

ans = N-K+1 - (sum(kaburi)+max(order_count-1, 0))
print(ans)

Submission status: Wrong Answer

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

ini_list = sorted(p[:k])
ini_min = min(p[:k])
ini_max = max(p[:k])

ans = 1

cnt_min = ini_min
cnt_max = ini_max
cnt_list = ini_list

for i in range(n-k):
    #print(i,ans)
    if cnt_min == p[i] and cnt_max <= p[k+i]:
        ans = ans
    else:
        ans += 1
    
    idx = bisect.bisect_left(cnt_list,p[i])
    del cnt_list[idx]
    
    idx = bisect.bisect_left(cnt_list,p[k+i])
    cnt_list.insert(idx,p[k+i])
    
    cnt_min = cnt_list[0]
    cnt_max = cnt_list[k-1]

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
L = LI()
l = 0
r = k
cnt = 1
ret = 0
a = 0
for i in range(n - 1):
    if L[i] < L[i + 1]:
        ret += 1
    else:
        if ret >= k - 1:
            a += 1
        ret = 0

if ret >= k - 1:
    a += 1


for l in range(n - k):
    if L[l] > L[l + 1] or L[l + k - 1] > L[l + k]:
        cnt += 1


print(cnt - (a - 1))

Submission status: Wrong Answer

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

if n == k:
    if p == sorted(p):
        print(1)
    else:
        print(2)
    exit()

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 update(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+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 = float('inf')
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
init(q)
for i in range(len(p)):
    update(i+1,p[i])

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 update1(k,x):
    k += num-1
    seg1[k] = x
    while k+1:
        k = (k-1)//2
        seg1[k] = segfunc1(seg1[k*2+1],seg1[k*2+2])
    
def query1(p,q):
    if q<=p:
        return ide_ele1
    p += num-1
    q += num-2
    res=ide_ele1
    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_ele1 = -1
#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg1=[ide_ele]*2*num
init(r)
for i in range(len(p)):
    update1(i+1,p[i])

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

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

print(ans)