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:
from collections import deque

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

min_d = deque()
max_d = deque()

v = 0


def append_p():
    while len(min_d) > 0 and p[min_d[-1]] > p[i]:
        min_d.pop()
    min_d.append(i)

    while len(max_d) > 0 and p[max_d[-1]] < p[i]:
        max_d.pop()
    max_d.append(i)

    if len(min_d) == k:
        global v
        v += 1


count = 1
for i in range(k):
    append_p()

for i in range(k, n):
    min_index = min_d[0]
    if min_index == i - k:
        min_d.popleft()

    append_p()

    max_index = max_d[0]
    if max_index == i - k:
        max_d.popleft()

    if min_index != i - k or max_index != i:
        count += 1

if v > 1:
    count -= (v - 1)

print(count)

Submission status: Wrong Answer

Solution code:
import copy

N, K = map(int, input().split())
original = list(map(int,input().split()))
list_sort = []

for i in range(N-K+1):
    after = copy.deepcopy(original)
    after_pre = original
    after[i:i+3] = sorted(after_pre[i:i+3])

    if after in list_sort:
        continue
    else:
        list_sort.append(after)

print(len(list_sort))

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
M = 0
num = 1

for i in range(k - 1):
    if p[i] > p[i + 1]:
        num += 1
        break   
for i in range(n - k):
    if p[i + k -1] > p[i + k]:
        num += 1
    elif p[i] > p[i + 1]:
        for j in range(k-1):
            if p[i + j + 1] > p[i + j + 2]:
                num += 1
                break
            else:
                M = p[i + 1]
                for l in range(k - 2):
                    if M < p[i + l]:
                        M = p[i + l]
                if M > p[i + k - 1]:
                    num += 1

print(num)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
M = 0
num = 1

for i in range(k - 1):
    if p[i] > p[i + 1]:
        num += 1
        break   
for i in range(n - k):
    if p[i + k -1] > p[i + k]:
        num += 1
    elif p[i] > p[i + 1]:
        for j in range(k-1):
            if p[i + j + 1] > p[i + j + 2]:
                num += 1
                break
            else:
                M = p[i + 1]
                for l in range(k - 2):
                    if M < p[i + l + 1]:
                        M = p[i + l + 1]
                        print(M)
                if M > p[i + k - 1]:
                    num += 1

print(num)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
M = 0
num = 1

for i in range(k - 1):
    if p[i] > p[i + 1]:
        num += 1
        break   
for i in range(n - k):
    if p[i + k -1] > p[i + k]:
        num += 1
    elif p[i] > p[i + 1]:
        for j in range(k-1):
            if p[i + j + 1] > p[i + j + 2]:
                num += 1
                break
            else:
                M = p[i + 1]
                for l in range(k - 1):
                    if M < p[i + l + 1]:
                        M = p[i + l + 1]
                        print(M)
                if M > p[i + k - 1]:
                    num += 1

print(num)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
p = list(map(int, input().split()))
p = [(i, i) for i in p]
res = 0

#####単位元######
ide_ele = (N, 0)

#num:n以上の最小の2のべき乗
num = 2 ** (N - 1).bit_length()
seg = [ide_ele] * 2 * num

def segfunc(x, y):
  
  mini = min(x[0], y[0])
  maxi = max(x[1], y[1])
  return (mini, maxi) #ここ判定関数（ただし結合則があるもの）

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

init(p)
table = [0] * (N - 1)
s = 0
for i in range(N - 1):
  if p[i][0] < p[i + 1][0]:
    table[i] += 1
segsum = sum(table[: K - 1])
for i in range(N - K + 1):
  if segsum == K - 1:
    s += 1
  #print(i, i + K - 1)
  if i != N - K: segsum += table[i + K - 1] - table[i]
for i in range(1, N - K + 1):
  l = query(i, i + K)[0]
  r = query(i - 1, i + K - 1)[1]
  if p[i - 1][0] > l or p[i + K - 1][0] < r:
    res += 1
    #print(i, i + K - 1, p[: i] + sorted(p[i: i + K]) + p[i + K: ])
print(res + 1 + min(1 - s, 0))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
N, K = map(int, input().split())
p = list(map(int, input().split()))
unsorted = []
res = 0
for i in range(N):
  if p[i] != i:
    unsorted.append(i)
unsorted.sort()
visited = set()
#print(unsorted)
for i in range(N - K + 1):
  l = bl(unsorted, i)
  r = min(bl(unsorted, i + K - 1), N - 1)
  if l + K - 1 == r:
    r -= 1
  #print(l, r)
  if (l, r) in visited:
    continue
  else:
    res += 1
    visited.add((l, r))
print(res)
"""
resset = set()
for i in range(N - K + 1):
  resset.add("".join(list(map(str, p[: i] + sorted(p[i: i + K] + p[i + K: ])))))
print(len(resset))
"""

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
N, K = map(int, input().split())
p = list(map(int, input().split()))
unsorted = []
res = 0
for i in range(N - 1):
  if p[i - 1] > p[i]:
    unsorted.append(i)
unsorted.sort()
visited = set()
#print(unsorted)
for i in range(N - K + 1):
  l = bl(unsorted, i)
  r = min(bl(unsorted, i + K - 1), N - 1)
  #print(l, r)
  if (l, r) in visited:
    continue
  else:
    res += 1
    visited.add((l, r))
print(res)

Submission status: Wrong Answer

Solution code:
#B
n,k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

ans  = 0
same = 0
diff = 0
diff_ind = []
same_ind = []

for i in range(n-k+1):
    a = p[i:i+k][:]
    a.sort()
    #print(a)
    #print(p)
    if a==p[i:i+k]:
        same += 1
        same_ind.append(i)
    else:
        diff += 1
        diff_ind.append(i)
        
ans += diff
if same>0:
    ans += 1

p.append(-1)    
for i in diff_ind:
    a=p[i:i+k][:]
    if min(a)==a[0] and max(a)==a[-1]:
        ans -= 1

print(ans)

Submission status: Wrong Answer

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

a=list(map(int, input().split()))
b=list(map(int, input().split()))

answer=a[0] - a[1] + 1
for i in range(a[0]):
  if i+a[1]+2 > a[0]:
    break;
  c=b[i:i+a[1]+2]
  if min(c)==c[0] and max(c)==c[a[1]+1]:
    answer-=1

print(answer)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
from collections import deque
smin,smax=deque(),deque()
x,r,r2=0,1,0
for i,p in enumerate(P):
    while len(smin)>0 and P[smin[-1]]>p:
        smin.pop()
    smin.append(i)
    if smin[0]<=i-K:
        smin.popleft()
    while len(smax)>0 and P[smax[-1]]<p:
        smax.pop()
    smax.append(i)
    if smax[0]<=i-K:
        smax.popleft()
    if i>0 and P[i-1]<P[i]:
        x=min(x+1,K-1)
    else:
        x=0
    if i>=K and not (P[i-K]<P[smin[0]] and smax[0]==i):
        if x!=K-1:
            r+=1
        else:
            r2=1
print(r+1 if r2 else r)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]

num = 1

for i in range(k - 1):
  if p[i] > p[i + 1]:
    num += 1
    break   
for i in range(n - k):
  if p[i] > p[i + 1] or p[i + k -1] > p[i + k]:
    num += 1

print(num)

Submission status: Wrong Answer

Solution code:
N,K= (int(i) for i in input().split())
n = [int(x) for x in input().split()]
if K>=N:
        print(1)
        exit()
c = 1
for i in range(N-K):
        for j in range(K-1):
                if n[i+j] > n[i+j+1]:
                        c+=1
                        break
print(c)

Submission status: Wrong Answer

Solution code:
N,K= (int(i) for i in input().split())
n = [int(x) for x in input().split()]
c = 1
for i in range(N-K):
        for j in range(K-1):
                if n[i] - n[i+j+1] > 0:
                        c+=1
                        break;
print(c)

Submission status: Wrong Answer

Solution code:
N,K= (int(i) for i in input().split())
n = [int(x) for x in input().split()]
c = 1
for i in range(N-K):
        for j in range(K-1):
                if n[i] - n[i+j+1] < 0:
                        c+=1
                        break;
print(c)

Submission status: Wrong Answer

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

x = n-k+1

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

Submission status: Wrong Answer

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

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

count=0
A=False
for i in range(N-K+1):
  p=P[i:i+K]
  q=sorted(p)
  if i>=1:
    if sorted(P[i-1:i-1+K])[1:]!=q[:-2]:
      if p!=q:
        count+=1
  if p==q:
    A=True
if A:
  count+=1

Submission status: Wrong Answer

Solution code:
from collections import deque

n,k=map(int,input().split())
p=list(map(int,input().split()))+[1000000]

p1=[0]*(n)
pmin=[0]*(n+1)
pmax=[0]*(n+1)

cnt=0

for i in range(n-1):
  if p[i]<p[i+1]:
    cnt+=1
  else:
    cnt=0
  p1[i+1]=cnt

d=deque()
d.append(0)

for i in range(1,k+1):
  if p[d[-1]]<p[i]:
    d.append(i)
  else:
    try:
      while p[d[-1]]>p[i]:
        d.pop()
    except:
      pass
    d.append(i)
pmin[k]=p[d[0]]

for i in range(k+1,n):
  if d[0]==i-(k+1):
    d.popleft()
  if p[d[-1]]<p[i]:
    d.append(i)
  else:
    try:
      while p[d[-1]]>p[i]:
        d.pop()
    except:
      pass
    d.append(i)
  pmin[i]=p[d[0]]


dd=deque()
dd.append(0)

for i in range(1,k+1):
  if p[dd[-1]]>p[i]:
    dd.append(i)
  else:
    try:
      while p[dd[-1]]<p[i]:
        dd.pop()
    except:
      pass
    dd.append(i)
pmax[k]=p[dd[0]]

for i in range(k+1,n):
  if dd[0]==i-(k+1):
    dd.popleft()
  if p[dd[-1]]>p[i]:
    dd.append(i)
  else:
    try:
      while p[dd[-1]]<p[i]:
        dd.pop()
    except:
      pass
    dd.append(i)
  pmax[i]=p[dd[0]]

ans=n-k+1
f=1
ff=[0]*n
for i in range(n):
  if p1[i]>=k-1:
    ff[i]=1
    if f==0:
      ans-=1
    else:
      f=0

for i in range(n-k):
  if p[i]==pmin[i+k] and p[i+k]==pmax[i+k] and ff[i]==0 and ff[i+1]==0:
    ans-=1


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,k=map(int,input().split())
p=list(map(int,input().split()))+[1000000]

p1=[0]*(n)
pmin=[0]*(n+1)
pmax=[0]*(n+1)

cnt=0

for i in range(n-1):
  if p[i]<p[i+1]:
    cnt+=1
  else:
    cnt=0
  p1[i+1]=cnt

d=deque()
d.append(0)

for i in range(1,k+1):
  if p[d[-1]]<p[i]:
    d.append(i)
  else:
    try:
      while p[d[-1]]>p[i]:
        d.pop()
    except:
      pass
    d.append(i)
pmin[k]=p[d[0]]

for i in range(k+1,n):
  if d[0]==i-(k+1):
    d.popleft()
  if p[d[-1]]<p[i]:
    d.append(i)
  else:
    try:
      while p[d[-1]]>p[i]:
        d.pop()
    except:
      pass
    d.append(i)
  pmin[i]=p[d[0]]


dd=deque()
dd.append(0)

for i in range(1,k+1):
  if p[dd[-1]]>p[i]:
    dd.append(i)
  else:
    try:
      while p[dd[-1]]<p[i]:
        dd.pop()
    except:
      pass
    dd.append(i)
pmax[k]=p[dd[0]]

for i in range(k+1,n):
  if dd[0]==i-(k+1):
    dd.popleft()
  if p[dd[-1]]>p[i]:
    dd.append(i)
  else:
    try:
      while p[dd[-1]]<p[i]:
        dd.pop()
    except:
      pass
    dd.append(i)
  pmax[i]=p[dd[0]]

ans=n-k+1
f=1
for i in range(n):
  if p1[i]>=k-1:
    if f==0:
      ans-=1
    else:
      f=0
    
for i in range(n-k):
  if p[i]==pmin[i+k] and p[i+k]==pmax[i+k]:
    ans-=1

print(ans)

Submission status: Wrong Answer

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

    ans = 1
    for i in range(N - K):
        L = sorted(P[i: i + K + 1])
        if P[i] != L[0] or P[i + K] != L[-1]:
            ans += 1

    print(ans)
    
p_b()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
a=list(map(int, input().split()))
b=list(map(int, input().split()))

answer=a[0] - a[1]
for i in range(a[0]):
  if i+a[1]+2 > a[0]:
    break;
  c=b[i:i+a[1]+2]
  if min(c)==c[0] and max(c)==c[a[1]]:
    answer-=1

print(answer)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
a=list(map(int, input().split()))
b=list(map(int, input().split()))

answer=a[0] - a[1]
for i in range(a[0]):
  if i+a[1]+1 > a[0]:
    break;
  c=b[i:i+a[1]+2]
  if min(c)==c[0] and max(c)==c[a[1]]:
    answer-=1

print(answer)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
a=list(map(int, input().split()))
b=list(map(int, input().split()))

answer=a[0] - a[1]
for i in range(a[0]):
  if i+a[1]+1 > a[0]:
    break;
  c=b[i:i+a[1]+1]
  if min(c)==c[0] and max(c)==c[a[1]]:
    answer-=1

print(answer)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

n,k=MI()
a=LI()
na=[-i for i in a]
qs,ql=[],[]

def slidmin(a,k):
    n=len(a)
    b=[0 for i in range(n-k+1)]
    q=deque()
    for i in range(k):
        show(q)
        while q and a[q[-1]]>=a[i]:
            q.pop()
        q.append(i)
    b[0]=a[q[0]]
    s=len(q)
    rt=[0 for _ in range(n-k+1)]
    if s==k:
        rt[0]=1
    for i in range(k,n):
        show(q,i,a[q[0]])
        while q and a[q[-1]]>=a[i]:
            q.pop()
            s-=1
        q.append(i)
        s+=1
        if q[0]<=i-k:
            q.popleft()
            s-=1
        b[i-k+1]=a[q[0]]
    return rt,b

sz,m=slidmin(a,k)
sz,M=slidmin(na,k)
M=[-i for i in M]
ans=1
p=-1
c=0
for i in range(k):
    if p<a[i]:
        c+=1
    else:
        c=1
    p=a[i]

for i in range(n-k):
    if p<a[i]:
        c+=1
    else:
        c=1
    p=a[i]
    if a[i]==m[i] and a[i+k]==M[i+1] and c<k:
        pass
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

n,k=MI()
a=LI()
#a=[int(i) for i in range(n)]
na=[-i for i in a]
qs,ql=[],[]
[heappush(qs,a[i]) for i in range(k)]
[heappush(ql,na[i]) for i in range(k)]
show(qs,ql,a)
#heappush(ql,na[:k])
for i in range(n-k):
    heappush(ql,-a[i])
    M=-heappop(ql)
    heappush(qs,a[i])
    m=heappop(qs)
    #show(i,'m,M',m,M)
    

def slidmin(a,k):
    n=len(a)
    b=[0 for i in range(n-k+1)]
    q=deque()
    for i in range(k):
        show(q)
        while q and a[q[-1]]>=a[i]:
            q.pop()
        q.append(i)
    b[0]=a[q[0]]
    s=len(q)
    rt=[0 for _ in range(n-k+1)]
    if s==k:
        rt[0]=1
    for i in range(k,n):
        show(q,i,a[q[0]])
        while q and a[q[-1]]>=a[i]:
            q.pop()
            s-=1
        q.append(i)
        s+=1
        if q[0]<=i-k:
            q.popleft()
            s-=1
        b[i-k+1]=a[q[0]]
    return rt,b

show('a',a)

sz,m=slidmin(a,k)
sz,M=slidmin(na,k)
M=[-i for i in M]
show(m,M,sz)
ans=1
p=-1
c=0
for i in range(k):
    if p<a[i]:
        c+=1
    else:
        c=1
    p=a[i]

for i in range(n-k):
    if p<a[i]:
        c+=1
    else:
        c=1
    p=a[i]
    show(i,a[i],m[i],a[i+k],M[i+1],a[:i]+sorted(a[i:i+k])+a[i+k:],c)
    if a[i]==m[i] and a[i+k]==M[i+1] and c<k:
        pass
        show(i,'pass')
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

n,k = map(int,input().split())
p = list(map(int,input().split()))
l_list = []
ans = 1
flag = False

tmp = copy.deepcopy(p)

l = tmp[:k]
l.sort()
l_list.append(l)

for i in range(1,n-k+1):
	l = tmp[i:i+k]
	l.sort()
	l_list.append(l)
	if p[i:i+k] == l:
		flag = True
		continue

	s1 = l_list[i-1]
	s2 = l_list[i]

	if s1[1:] == s2[:-1]:
		continue
	else:
		ans += 1

if flag:
	print(ans+1)
else:
	print(ans)

Submission status: Wrong Answer

Solution code:
import copy

n,k = map(int,input().split())
p = list(map(int,input().split()))
l_list = []
ans = 1
flag = False

tmp = copy.deepcopy(p)

l = tmp[:k]
l.sort()
l_list.append(l)

for i in range(1,n-k+1):
	l = tmp[i:i+k]
	tmp2 = copy.deepcopy(l)
	l.sort()
	l_list.append(l)
	if tmp2 == l:
		flag = True
		continue

	s1 = l_list[i-1]
	s2 = l_list[i]

	if s1[1:] == s2[:-1]:
		continue
	else:
		ans += 1

if flag:
	print(ans+1)
else:
	print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
(n,k),p = [list(map(int, s.split())) for s in open(0)]
p = np.array(p)

p_isordered = p[1:]>p[:-1]
p_cumsum = p_isordered.cumsum()

ans = n - k + 1
no_change = False
if p_cumsum[k-2]==k-1:
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
(n,k),p = [list(map(int, s.split())) for s in open(0)]
p = np.array(p)

p_isordered = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
if p_isordered[:k-1].all():
    no_change = True

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

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
(n,k),p = [list(map(int, s.split())) for s in open(0)]
p = np.array(p)

p_isorder = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
if p_isorder[:k-1].all():
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if p_isorder[i+1:i+k].all():
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

Submission status: Wrong Answer

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

p_isorder = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
for j in range(k-1):
    if not p_isorder[j]:
        break
else:
    no_change = True

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

print(ans)
print(0)

Submission status: Wrong Answer

Solution code:
import collections
import heapq
import sys

input = sys.stdin.readline


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

        hq = []
        ans = 0
        for i in range(0, K):
            v = -1 * P[i]
            if v == 0:
                v =1
            heapq.heappush(hq, v)
            if hq[0] != v:
                ans = 1

        for i in range(K, N):
            v = -1 * P[i]
            if v == 0:
                v =1
            heapq.heappush(hq, v)
            if hq[0] != v:
                ans += 1
            hq = hq[:K]

        print(max(1,ans))



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

Submission status: Wrong Answer

Solution code:
import collections
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        ans = 0
        q = collections.deque()
        tmp = 0
        for i, v in enumerate(input().split()):
            if int(v) != i:
                q.append(True)
                first = True
                tmp += 1
            else:
                q.append(False)
                first = False

            if i + 1 >= K:
                last = q.popleft()
                if tmp > 0 and (first or last):
                    ans += 1
                if last:
                    tmp -= 1

        print(max(1, ans))


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

Submission status: Wrong Answer

Solution code:
INF = float('inf')

class SegmentTree:
    def __init__(self, size):
        self._size = (1 << size.bit_length())
        self._data = [INF] * (self._size * 2)

    def update(self, index, value):
        index += self._size - 1
        self._data[index] = value
        while index > 0:
            index = (index - 1) // 2
            self._data[index] = min(self._data[index * 2 + 1], self._data[index * 2 + 2])

    def __query(self, qLeft, qRight, node, left, right):
        if right <= qLeft or qRight <= left:
            return INF
        if qLeft <= left and right <= qRight:
            return self._data[node]

        leftVal = self.__query(qLeft, qRight, node * 2 + 1, left, (left + right) // 2)
        rightVal = self.__query(qLeft, qRight, node * 2 + 2, (left + right) // 2, right)
        return min(leftVal, rightVal)

    def query(self, left, right):
        return self.__query(left, right, 0, 0, self._size)

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

minTree = SegmentTree(N)
maxTree = SegmentTree(N)

for i, p in enumerate(P):
    minTree.update(i, p)
    maxTree.update(i, -p)

ans = 1
hasSame = False
seq = 1
for i in range(1, K):
    if P[i - 1] < P[i]:
        seq += 1
    else:
        seq = 1
if seq >= K:
    hasSame = True

for left in range(N - K):
    right = left + K

    if P[right - 1] < P[right]:
        seq += 1
    else:
        seq = 1

    if minTree.query(left, right) == P[left] and maxTree.query(left + 1, right + 1) == P[right]:
        continue
    else:
        if seq >= K:
            if hasSame:
                continue
            else:
                hasSame = True
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left, bisect_right
    N, K = map(int, input().split())
    P = [int(x) for x in input().split()]

    A = [0]
    prev = P[0]

    for i in range(1, N):
        p = P[i]
        if prev > p:
            A.append(i)
        prev = p
    A.append(N)
    #print(A)
    #for s, t in zip(A, A[1:]): print((s, t), P[s:t])

    prev = None
    c = 0
    for i in range(N-K+1):
        s = i
        t = i + K
        j = bisect_right(A, s)
        k = bisect_left(A, t)
        if (j, k) != prev:
            #print(j,k, P[s:t])
            c += 1
        prev = (j,k)
    print(c)
main()

Submission status: Wrong Answer

Solution code:
import bisect

import sys
input = sys.stdin.readline

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:
#!/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
que = deque()
que.append(0)
minlst = []
for i in range(1,n):
    if p[que[-1]] < p[i]:
        que.append(i)
    else:
        while que:
            if p[que[-1]] < p[i]:
                que.append(i)
                break
            else:
                que.pop()
        else:
            que.append(i)
    if i >= k:
        minlst.append(p[que[0]])
        if que[0] == i - k:
            que.popleft()
minlst.append(p[que[0]])
que = deque()
que.append(0)
maxlst = []
for i in range(1,n):
    if p[que[-1]] > p[i]:
        que.append(i)
    else:
        while que:
            if p[que[-1]] > p[i]:
                que.append(i)
                break
            else:
                que.pop()
        else:
            que.append(i)
    if i >= k-1:
        maxlst.append(p[que[0]])
        if que[0] == i - k:
            que.popleft()
ans = 1
for i in range(n-k):
    if maxlst[i] < maxlst[i+1] and minlst[i] < minlst[i+1]:
        continue
    ans += 1
cnt = 1
tmp = p[0]
lst = []
for i in range(1,n):
    if tmp < p[i]:
        cnt += 1
    else:
        lst.append(cnt)
        cnt = 1
    tmp = p[i]
lst.append(cnt)
cnt = 0
flg = False
for i in lst:
    if i >= k:
        cnt += 1
    if cnt == 2:
        flg = True
if flg:
    ans -= 1
print(ans)

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
que = deque()
que.append(0)
minlst = []
for i in range(1,n):
    if p[que[-1]] < p[i]:
        que.append(i)
    else:
        while que:
            if p[que[-1]] < p[i]:
                que.append(i)
                break
            else:
                que.pop()
        else:
            que.append(i)
    if i >= k:
        minlst.append(p[que[0]])
        if que[0] == i - k:
            que.popleft()
minlst.append(p[que[0]])
que = deque()
que.append(0)
maxlst = []
for i in range(1,n):
    if p[que[-1]] > p[i]:
        que.append(i)
    else:
        while que:
            if p[que[-1]] > p[i]:
                que.append(i)
                break
            else:
                que.pop()
        else:
            que.append(i)
    if i >= k-1:
        maxlst.append(p[que[0]])
        if que[0] == i - k:
            que.popleft()
ans = 1
for i in range(n-k):
    if maxlst[i] < maxlst[i+1] and minlst[i] < minlst[i+1]:
        continue
    ans += 1
cnt = 1
tmp = p[0]
lst = []
for i in range(1,n):
    if tmp < p[i]:
        cnt += 1
    else:
        lst.append(cnt)
        cnt = 1
    tmp = p[i]
lst.append(cnt)
tmp = 0
flg1,flg2 = False,False
for i in lst:
    if i >= k:
        if flg1:
            flg2 = True
        flg1 = True
        tmp += i - k + 1
if flg1 & flg2:
    ans -= tmp
    ans += 1
print(ans)

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
que = deque()
que.append(0)
minlst = []
for i in range(1,n):
    if p[que[-1]] < p[i]:
        que.append(i)
    else:
        while que:
            if p[que[-1]] < p[i]:
                que.append(i)
                break
            else:
                que.pop()
        else:
            que.append(i)
    if i >= k:
        minlst.append(p[que[0]])
        if que[0] == i - k:
            que.popleft()
minlst.append(p[que[0]])
que = deque()
que.append(0)
maxlst = []
for i in range(1,n):
    if p[que[-1]] > p[i]:
        que.append(i)
    else:
        while que:
            if p[que[-1]] > p[i]:
                que.append(i)
                break
            else:
                que.pop()
        else:
            que.append(i)
    if i >= k-1:
        maxlst.append(p[que[0]])
        if que[0] == i - k:
            que.popleft()
s = set()
for i in range(n-k+1):
    s.add((maxlst[i],minlst[i]))
ans = len(s)
cnt = 1
tmp = p[0]
lst = []
for i in range(1,n):
    if tmp < p[i]:
        cnt += 1
    else:
        lst.append(cnt)
        cnt = 1
    tmp = p[i]
lst.append(cnt)
tmp = 0
flg1,flg2 = False,False
for i in lst:
    if i >= k:
        if flg1:
            flg2 = True
        flg1 = True
        tmp += i - k + 1
if flg1 & flg2:
    ans -= tmp
    ans += 1
print(ans)