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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, P):
    hmax = []
    hmin = []
    for i in range(K):
        heapq.heappush(hmax, -P[i])
        heapq.heappush(hmin, P[i])
    
    a = []
    for p0, p1 in zip(P, P[1:]):
        a.append(1 if p1 > p0 else -1)
    
    sa = [0]
    for b in a:
        sa.append(sa[-1] + b)


    ss = 0
    for i in range(N-K+1):
        if sa[i+K-1] - sa[i] == K-1:
            ss += 1
    
    ans = 1
    used = set()
    for i in range(N-K):
        l = P[i]
        r = P[i+K]
        heapq.heappush(hmax, -r)
        if l != hmin[0] or r != -hmax[0]:
            ans += 1

        heapq.heappush(hmin, r)
        used.add(l)
        while hmin[0] in used:
            heapq.heappop(hmin)
        while -hmax[0] in used:
            heapq.heappop(hmax)

    # if ss >= 2:
    ans -= ss - 1

    return ans 


def main():
    N, K = read_int_n()
    P = read_int_n()
    print(slv(N, K, P))

    # N = 200000
    # K = random.randint(1, N-1)
    # P = list(range(N))
    # random.shuffle(P)

    # N = 5
    # K = 2
    # P = [2,4, 0, 3, 1]
    # print(N, K)
    # print(' '.join(map(str, P)))

    # print(slv(N, K, P))
    


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, P):
    hmax = []
    hmin = []
    for i in range(K):
        heapq.heappush(hmax, -P[i])
        heapq.heappush(hmin, P[i])
    
    a = []
    for p0, p1 in zip(P, P[1:]):
        a.append(1 if p1 > p0 else -1)
    
    sa = [0]
    for b in a:
        sa.append(sa[-1] + b)


    ss = 0
    for i in range(N-K+1):
        if sa[i+K-1] - sa[i] == K-1:
            ss += 1
    
    ans = 1
    used = set()
    for i in range(N-K):
        l = P[i]
        r = P[i+K]
        heapq.heappush(hmax, -r)
        if l != hmin[0] or r != -hmax[0]:
            ans += 1

        heapq.heappush(hmin, r)
        used.add(l)
        while hmin[0] in used:
            heapq.heappop(hmin)
        while -hmax[0] in used:
            heapq.heappop(hmax)

    if ss >= 2:
        ans -= ss - 1

    return ans 


def main():
    N, K = read_int_n()
    P = read_int_n()
    print(slv(N, K, P))

    # N = 200000
    # K = random.randint(1, N-1)
    # P = list(range(N))
    # random.shuffle(P)

    # N = 5
    # K = 2
    # P = [2,4, 0, 3, 1]
    # print(N, K)
    # print(' '.join(map(str, P)))

    # print(slv(N, K, P))
    


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
  def update(k,x):
    k+=N0-1
    data_min[k]=data_max[k]=x
    while k>=0:
      k=(k-1)//2
      a,b=data_min[2*k+1],data_min[2*k+2]
      data_min[k]=a if a<b else b
      a,b=data_max[2*k+1],data_max[2*k+2]
      data_max[k]=a if a>b else b
  def query_min(l,r):
    L,R=l+N0,r+N0
    s=INF
    while L<R:
      if R&1:
        R-=1
        t=data_min[R-1]
        if t<s:s=t
      if L&1:
        t=data_min[L-1]
        if t<s:s=t
        L+=1
      L//=2
      R//=2
    return s
  def query_max(l,r):
    L,R=l+N0,r+N0
    s=0
    while L<R:
      if R&1:
        R-=1
        t=data_max[R-1]
        if t>s:s=t
      if L&1:
        t=data_max[L-1]
        if t>s:s=t
        L+=1
      L//=2
      R//=2
    return s
  def root(x):
    while table[x]>=0:x=table[x]
    return x
  def unite(x,y):
    x=root(x)
    y=root(y)
    if x!=y:
      if table[x]>table[y]:x,y=y,x
      table[x]+=table[y]
      table[y]=x
  def same(x,y):return root(x)==root(y)
  def size(x):return-table[root(x)]
  n,k,*p=map(int,open(0).read().split())
  N0=2**(n-1).bit_length()
  INF=10**18
  data_min=[INF]*2*N0
  data_max=[0]*2*N0
  table=[-1]*n
  c=[1]
  for a,b in zip(p,p[1:]):
    if a<b:c+=c[-1]+1,
    else:c+=1,
  for i,q in enumerate(p):update(i,q)
  for i,(a,b)in enumerate(zip(p,p[k:])):
    if a==query_min(i,i+k)and b==query_max(i+1,i+k+1):unite(i,i+1)
  c=sum(t>=k for t in c)
  print(n-k+1-len(set(t for t in table if t>=0))-c*(c-1)//2)
main()

Submission status: Wrong Answer

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

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

def is_sorted(sub_arr):
  for i in range(1, len(sub_arr)):
    if sub_arr[i] < sub_arr[i-1]:
      return False
  return True

prev_sorted = is_sorted(arr[:K])
up_count = 1
for i in range(K-1,1,-1):
  if arr[i] > arr[i-1]:
    up_count += 1
  else:
    break
if prev_sorted:
  sort_count = 1
else:
  sort_count = 0
count = 1
for i in range(K, N):
  sub = sorted(arr[i-K:i])
  if arr[i] > sub[-1]:
    if up_count == K-1:
      prev_sorted = True
      sort_count += 1
    else:
      up_count = (up_count+1)%K

    if not prev_sorted:
      if arr[i-K] == sub[0]:
        pass
      else:
        count += 1
  else:
    up_count = 1
    count += 1
    prev_sorted = False

count -= max(0,(sort_count - 1))
print(max(1, count))

Submission status: Wrong Answer

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

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

def is_sorted(sub_arr):
  for i in range(1, len(sub_arr)):
    if sub_arr[i] < sub_arr[i-1]:
      return False
  return True

prev_sorted = is_sorted(arr[:K])
up_count = 1
for i in range(K-1,1,-1):
  if arr[i] > arr[i-1]:
    up_count += 1
  else:
    break
if prev_sorted:
  sort_count = 1
else:
  sort_count = 0
count = 1
for i in range(K, N):
  if arr[i] > max(arr[i-K+1:i]):
    if up_count == K-1:
      prev_sorted = True
      sort_count += 1
    else:
      up_count = (up_count+1)%K

    if not prev_sorted:
      count += 1
  else:
    up_count = 1
    count += 1
    prev_sorted = False

count -= (sort_count - 1)
print(max(1, count))

Submission status: Wrong Answer

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

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

def is_sorted(sub_arr):
  for i in range(1, len(sub_arr)):
    if sub_arr[i] < sub_arr[i-1]:
      return False
  return True

prev_sorted = is_sorted(arr[:K])
up_count = 0
count = 0
for i in range(K, N):
  if arr[i] > max(arr[i-K+1:i]):
    if up_count == K-1:
      prev_sorted = True
    else:
      up_count = (up_count+1)%K

    if not prev_sorted:
      count += 1
    continue
  else:
    up_count = 0
    count += 1
    prev_sorted = False


print(max(1, count))

Submission status: Wrong Answer

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


total = 0
for i in range(1, N-K+1):
  semin = sorted(arr[i-1:i+K-2])[1]
  if semin == min(arr[i:i+K-1]) and max(arr[i:i+K]) == arr[i+K-1]:
    pass
  else:
    total += 1

print(max(1, total))

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
p = tuple(map(int, input().split()))
dp = np.zeros(n+1)
dp[k:] += 1
for i in range(k, n):
    if max(p[i-k:i-1]) > p[i]:
        dp[i+1:] += 1
    elif min(p[i-k+1:i-1]) < p[i-k]:
        dp[i+1:] += 1
print(int(dp[n]))

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
p = tuple(map(int, input().split()))
dp = np.zeros(n+1)
dp[k] = 1
for i in range(k, n):
    if max(p[i-k:i-1]) > p[i]:
        dp[i+1] = dp[i] + 1
    elif min(p[i-k+1:i-1]) < p[i-k]:
        dp[i+1] = dp[i] + 1
    else:
        dp[i+1] = dp[i]
print(dp[n])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
dp = [0]*(n+1)
dp[k] = 1
for i in range(k, n):
    if max(p[i-k:i-1]) > p[i]:
        dp[i+1] = dp[i] + 1
    elif min(p[i-k+1:i-1]) < p[i-k]:
        dp[i+1] = dp[i] + 1
    else:
        dp[i+1] = dp[i]
print(dp[n])

Submission status: Wrong Answer

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

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

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

S = many_int()

length = len(S)
count=0
flg=True
i=0
while i < (length-K):
    temp = S[i:i+K]
    sorts =sorted(temp)
    temp_i = 0
    for ind,(ii, jj) in enumerate(zip(temp,sorts)):
        if ii!=jj:
            temp_i = ind
    
    if temp_i != 0:
        count += temp_i
        i+= temp_i
    elif flg:
        count+=1
        flg=False
        i+=1
    else:
        i+=1
if K == len(S):
    count += 1
print(count)

Submission status: Wrong Answer

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

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

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

S = many_int()

length = len(S)
count=0
flg=True
for i in range(length-K):
    temp = S[i:i+K]
    if temp != sorted(temp):
        count+=1
    elif flg:
        count+=1
        flg=False
if K == len(S):
    count += 1
print(count)

Submission status: Wrong Answer

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

def isInc(numList):
    for i in range(len(numList)-1):
        if numList[i]>numList[i+1]:
            return False
    return True

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

count = 1
for i in range(n-k+1):
    if not isInc(p[i:i+k]):
        count+=1
    
print(count)

Submission status: Wrong Answer

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

def isSorted(A):
    for i in range(len(A) - 1):
        if A[i + 1] < A[i]:
            return False

    return True

count = 1
for i in range(len(P) - K):
    if isSorted(P[i : i + K]):
        pass
    else:
        count += 1

print(count)

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 = ini_list[0]
ini_max = ini_list[k-1]

#print(ini_list,ini_min,ini_max)
#exit()

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] or cnt_max > p[k+i]:
        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:
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] or cnt_max > p[k+i]:
        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:
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:
import sys
input = sys.stdin.readline

# 二部探索木の代わり
# max_Xが大きい場合、0を含む場合は座標圧縮する

class BITbisect():
    def __init__(self, max_X):
        self.max_X = max_X + 1
        self.bit = [0]*(self.max_X+1)

    # x番目にaを加える
    def add(self, x, a):
        while x <= self.max_X:
            self.bit[x] += a
            x += x & -x

    def insert(self, x):
        self.add(x, 1)

    def delete(self, x):
        self.add(x, -1)

    # xまでに出現している個数
    def query_sum(self, x):
        s = 0
        while x > 0:
            s += self.bit[x]
            x -= x & -x
        return s

    def exist(self, x):
        if self.query_sum(x) - self.query_sum(x-1) > 0:
            return True
        return False
    
    def count(self, x):
        return self.query_sum(x) - self.query_sum(x-1)

    # xより大きくてbitに入ってるもののうち最小のもの
    # O((logN)^2)
    def upper(self, x):
        qx = self.query_sum(x) + 1
        if qx > self.query_sum(self.max_X):
            return False
        l = 0
        r = self.max_X
        while l < r:
            m = (l+r)//2
            if self.query_sum(m) < qx:
                if l == m:
                    return r
                l = m
            else:
                r = m
        if m == self.max_X:
            return False
        return m

    # x以下でbitに入っているもののうち最大のもの
    # O((logN)^2)
    def lower(self, x):
        qx = self.query_sum(x)
        if qx == 0:
            return False
        l = 0
        r = self.max_X
        while r-l > 1:
            m = (l+r)//2
            if self.query_sum(m) < qx:
                l = m
            else:
                r = m
        if l == 0:
            return False
        return l

    # listみたいに表示
    def display(self):
        print('inside BIT:', end=' ')
        for x in range(1, self.max_X):
            if bit.exist(x):
                c = bit.count(x)
                for _ in range(c):
                    print(x, end=' ')
        print()

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

    bit = BITbisect(N+1)
    for i in range(K):
        bit.insert(P[i]+1)
    c = 0
    for j in range(N-K):
        if bit.lower(P[j]+1) is False and bit.upper(P[j+K]+1) is False:
            c += 1
        bit.delete(P[j]+1)
        bit.insert(P[j+K]+1)


    k = -1
    l = 0
    same = 0
    for i in range(N):
        if P[i] > k:
            l += 1
        else:
            l = 1
        k = P[i]
        if l >= K:
            same += 1

    print(N-K+1-c-max(0, same-1))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from collections import deque

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    maxstack = deque([])
    minstack = deque([])
    for i in range(k):
        while len(minstack) != 0 and p[minstack[-1]] >= p[i]:
            minstack.pop()
        minstack.append(i)
        while len(maxstack) != 0 and p[maxstack[-1]] <= p[i]:
            maxstack.pop()
        maxstack.append(i)

    swap = [0]
    for i in range(n-1):
        if p[i] > p[i+1]:
            swap.append(swap[-1]+1)
        else:
            swap.append(swap[-1])

    ans = 0
    swapa = 1 if swap[k-1] - swap[0] == 0 else 0
    for i in range(k, n):
        is_cont = True
        while minstack[0] < i-k:
            minstack.popleft()
        if p[minstack[0]] != p[i-k]:
            is_cont = False
        while len(minstack) != 0 and p[minstack[-1]] >= p[i]:
            minstack.pop()
        minstack.append(i)
        
        while maxstack[0] < i-k+1:
            maxstack.popleft()
        if p[maxstack[0]] != p[i]:
            is_cont = False
        while len(maxstack) != 0 and p[maxstack[-1]] <= p[i]:
            maxstack.pop()
        maxstack.append(i)

        if swap[i] - swap[i-k+1] == 0 and is_cont:
            swapa = 1
            continue

        if not is_cont:
            ans += 1

    print(ans + swapa)    
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from collections import deque

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    maxstack = deque([])
    minstack = deque([])
    for i in range(k):
        while len(minstack) != 0 and p[minstack[-1]] >= p[i]:
            minstack.pop()
        minstack.append(i)
        while len(maxstack) != 0 and p[maxstack[-1]] <= p[i]:
            maxstack.pop()
        maxstack.append(i)

    swap = [0]
    for i in range(n-1):
        if p[i] > p[i+1]:
            swap.append(swap[-1]+1)
        else:
            swap.append(swap[-1])

    ans = 0
    swapa = 1 if swap[k-1] - swap[0] == 0 else 0
    for i in range(k, n):
        is_cont = True
        while minstack[0] < i-k+1:
            minstack.popleft()
        if p[minstack[0]] != p[i-k]:
            is_cont = False
        while len(minstack) != 0 and p[minstack[-1]] >= p[i]:
            minstack.pop()
        minstack.append(i)
        
        while maxstack[0] < i-k+2:
            maxstack.popleft()
        if p[maxstack[0]] != p[i]:
            is_cont = False
        while len(maxstack) != 0 and p[maxstack[-1]] <= p[i]:
            maxstack.pop()
        maxstack.append(i)

        if swap[i-1] - swap[i-k] == 0:
            swapa = 1
            continue

        if not is_cont:
            ans += 1

    print(ans + swapa)    
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from collections import deque

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    maxstack = deque([])
    minstack = deque([])
    for i in range(k):
        while len(minstack) != 0 and p[minstack[-1]] >= p[i]:
            minstack.popleft()
        minstack.append(i)
        while len(maxstack) != 0 and p[maxstack[-1]] <= p[i]:
            maxstack.popleft()
        maxstack.append(i)
    
    ans = 1 if p[minstack[0]] != p[0] or p[maxstack[0]] != p[k-1] else 0
    for i in range(k, n):
        is_cont = True

        if p[minstack[0]] != p[i-k]:
            is_cont = False
        while len(minstack) != 0 and p[minstack[-1]] >= p[i]:
            minstack.pop()
        minstack.append(i)
        while len(maxstack) != 0 and p[maxstack[-1]] <= p[i]:
            maxstack.pop()
        maxstack.append(i)
        if p[maxstack[0]] != p[i]:
            is_cont = False
        
        if i == k or is_cont:
            continue
        else:
            ans += 1
    
    swapi = []
    for i in range(1, n):
        if p[i-1] > p[i]:
            swapi.append(i)
    swapi.append(n)

    tmpa = 0
    overa = 0
    for i in range(len(swapi)-1):
        if swapi[i+1] - swapi[i] >= k:
            if tmpa == 0:
                tmpa = 1
            else:
                overa += 1
    print(ans + tmpa - overa)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from collections import deque

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    maxstack = deque([])
    minstack = deque([])
    for i in range(k):
        while len(minstack) != 0 and p[minstack[-1]] >= p[i]:
            minstack.popleft()
        minstack.append(i)
        while len(maxstack) != 0 and p[maxstack[-1]] <= p[i]:
            maxstack.popleft()
        maxstack.append(i)
    
    ans = 1 if p[minstack[0]] != p[0] or p[maxstack[0]] != p[k-1] else 0
    for i in range(k, n):
        is_cont = True

        if p[minstack[0]] != p[i-k]:
            is_cont = False
        while len(minstack) != 0 and p[minstack[-1]] >= p[i]:
            minstack.pop()
        minstack.append(i)
        while len(maxstack) != 0 and p[maxstack[-1]] <= p[i]:
            maxstack.pop()
        maxstack.append(i)
        if p[maxstack[0]] != p[i]:
            is_cont = False
        
        if i == k or is_cont:
            continue
        else:
            ans += 1
    
    swapi = [0]
    for i in range(1, n):
        if p[i-1] > p[i]:
            swapi.append(i)
    swapi.append(n)

    tmpa = 0
    overa = 0
    for i in range(len(swapi)-1):
        if swapi[i+1] - swapi[i] >= k:
            if tmpa == 0:
                tmpa = 1
            else:
                overa += 1
    print(ans + tmpa - overa)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

# for i in range(n-k+1):
#     pp = P[i:i+k]
#     pp.sort()
#     print(P[:i] + pp + P[i+k:])

A = []
B = []
VA = [0] * n
VB = [0] * n
import heapq
for i in range(k):
    heapq.heappush(A, P[i])  # 最小値用
    heapq.heappush(B, -P[i])  # 最大値用

ans = 1
for i in range(n-k):
    b = -heapq.heappop(B)
    while VB[b] == 1:
        b = -heapq.heappop(B)
    a = heapq.heappop(A)
    while VA[a] == 1:
        a = heapq.heappop(A)
    # print(i,a,b,A,B)
    # print(P[k+i] ,b ,P[i] , a)
    if not(P[k+i] > b and P[i] == a):
        ans += 1
        # print(i)
    heapq.heappush(A, a)
    heapq.heappush(B, -b) 
    heapq.heappush(A, P[k+i])
    heapq.heappush(B, -P[k+i])

    VA[P[i]] = 1
    VB[P[i]] = 1

AA = []
for i in range(n-1):
    if P[i+1] - P[i] >= 0:
        AA.append(1)
    else:
        AA.append(0)
s = sum(AA[:k-1])
t = 0
r = 0
if s == k-1:
    t += 1
    r = 1
for i in range(n-k):
    # print(AA)
    s += AA[k-1+i]
    s -= AA[i]
    if s == k-1:
        t += 1
        r += 1
    else:
        ans -= max(0, r-1)
        r = 0
ans -= max(0, r-1)
# print("t",t)
print(ans - max(0, t-1))

Submission status: Wrong Answer

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

# for i in range(n-k+1):
#     pp = P[i:i+k]
#     pp.sort()
#     print(P[:i] + pp + P[i+k:])

A = []
B = []
VA = [0] * n
VB = [0] * n
import heapq
for i in range(k):
    heapq.heappush(A, P[i])  # 最小値用
    heapq.heappush(B, -P[i])  # 最大値用

ans = 1
for i in range(n-k):
    b = -heapq.heappop(B)
    while VB[b] == 1:
        b = -heapq.heappop(B)
    a = heapq.heappop(A)
    while VA[a] == 1:
        a = heapq.heappop(A)
    # print(i,a,b,A,B)
    # print(P[k+i] ,b ,P[i] , a)
    if not(P[k+i] > b and P[i] == a):
        ans += 1
        # print(i)
    heapq.heappush(A, a)
    heapq.heappush(B, -b) 
    heapq.heappush(A, P[k+i])
    heapq.heappush(B, -P[k+i])

    VA[P[i]] = 1
    VB[P[i]] = 1

AA = []
for i in range(n-1):
    if P[i+1] - P[i] >= 0:
        AA.append(1)
    else:
        AA.append(0)
s = sum(AA[:k-1])
t = 0
r = 0
if s == k-1:
    t += 1
    r = 1
for i in range(n-k):
    # print(AA)
    s += AA[k-1+i]
    s -= AA[i]
    if s == k-1:
        t += 1
        r += 1
    else:
        ans -= max(0, r-1)
        r = 0
# print("t",t)
print(ans - max(0, t-1))

Submission status: Wrong Answer

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

# for i in range(n-k+1):
#     pp = P[i:i+k]
#     pp.sort()
#     print(P[:i] + pp + P[i+k:])

A = []
B = []
VA = [0] * n
VB = [0] * n
import heapq
for i in range(k):
    heapq.heappush(A, P[i])  # 最小値用
    heapq.heappush(B, -P[i])  # 最大値用

ans = 1
for i in range(n-k):
    b = -heapq.heappop(B)
    while VB[b] == 1:
        b = -heapq.heappop(B)
    a = heapq.heappop(A)
    while VA[a] == 1:
        a = heapq.heappop(A)
    # print(i,a,b,A,B)
    # print(P[k+i] ,b ,P[i] , a)
    if not(P[k+i] > b and P[i] == a):
        ans += 1
        # print(i)
    heapq.heappush(A, a)
    heapq.heappush(B, -b) 
    heapq.heappush(A, P[k+i])
    heapq.heappush(B, -P[k+i])

    VA[P[i]] = 1
    VB[P[i]] = 1

AA = []
for i in range(n-1):
    if P[i+1] - P[i] >= 0:
        AA.append(1)
    else:
        AA.append(0)
s = sum(AA[:k-1])
t = 0
r = 0
if s == k-1:
    t += 1
    r = 1
for i in range(n-k):
    # print(AA)
    s += AA[k-1+i]
    s -= AA[i]
    if s == k-1:
        t += 1
        r += 1
    else:
        ans -= max(0, r-1)
# print("t",t)
print(ans - max(0, t-1))

Submission status: Wrong Answer

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

# for i in range(n-k+1):
#     pp = P[i:i+k]
#     pp.sort()
#     print(P[:i] + pp + P[i+k:])

A = []
B = []
VA = [0] * n
VB = [0] * n
import heapq
for i in range(k):
    heapq.heappush(A, P[i])  # 最小値用
    heapq.heappush(B, -P[i])  # 最大値用

ans = 1
for i in range(n-k):
    b = -heapq.heappop(B)
    while VB[b] == 1:
        b = -heapq.heappop(B)
    a = heapq.heappop(A)
    while VA[a] == 1:
        a = heapq.heappop(A)
    # print(i,a,b,A,B)
    # print(P[k+i] ,b ,P[i] , a)
    if not(P[k+i] > b and P[i] == a):
        ans += 1
        # print(i)
    heapq.heappush(A, a)
    heapq.heappush(B, -b) 
    heapq.heappush(A, P[k+i])
    heapq.heappush(B, -P[k+i])

    VA[P[i]] = 1
    VB[P[i]] = 1

AA = []
for i in range(n-1):
    if P[i+1] - P[i] >= 0:
        AA.append(1)
    else:
        AA.append(0)
s = sum(AA[:k-1])
t = 0
if s == k-1:
    t += 1
for i in range(n-k):
    # print(AA)
    s += AA[k-1+i]
    s -= AA[i]
    if s == k-1:
        t += 1
# print("t",t)
print(ans - max(0, t-1))

Submission status: Wrong Answer

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

for i in range(n-k+1):
    pp = P[i:i+k]
    pp.sort()
    # print(P[:i] + pp + P[i+k:])

A = []
B = []
VA = [0] * n
VB = [0] * n
import heapq
for i in range(k):
    heapq.heappush(A, P[i])  # 最小値用
    heapq.heappush(B, -P[i])  # 最大値用

ans = 1
for i in range(n-k):
    b = -heapq.heappop(B)
    while VB[b] == 1:
        b = -heapq.heappop(B)
    a = heapq.heappop(A)
    while VA[a] == 1:
        a = heapq.heappop(A)
    # print(i,a,b,A,B)
    # print(P[k+i] ,b ,P[i] , a)
    if not(P[k+i] > b and P[i] == a):
        ans += 1
        # print(i)
    heapq.heappush(A, a)
    heapq.heappush(B, -b) 
    heapq.heappush(A, P[k+i])
    heapq.heappush(B, -P[k+i])

    VA[P[i]] = 1
    VB[P[i]] = 1

AA = []
for i in range(n-1):
    if P[i+1] - P[i] >= 0:
        AA.append(1)
    else:
        AA.append(0)
s = sum(AA[:k-1])
t = 0
if s == k-1:
    t += 1
for i in range(n-k):
    # print(AA)
    s += AA[k-1+i]
    s -= AA[i]
    if s == k-1:
        t += 1
# print("t",t)
print(ans - max(0, t-1))

Submission status: Wrong Answer

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

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

def slide_min(n, k, p):
    res = [0] * n
    deq = [0] * n
    s = 0
    t = 0
    for i in range(n):
        while s < t:
            if p[deq[t-1]] >= p[i]:
                t -= 1
            else:
                break
        deq[t] = i
        t += 1
        if i-k+1 >= 0:
            res[i-k+1] = p[deq[s]]
            if deq[s] == i-k+1:
                s += 1
    return res

def slide_max(n, k, p):
    res = [0] * n
    deq = [0] * n
    s = 0
    t = 0
    for i in range(n):
        while s < t:
            if p[deq[t-1]] < p[i]:
                t -= 1
            else:
                break
        deq[t] = i
        t += 1
        if i-k+1 >= 0:
            res[i-k+1] = p[deq[s]]
            if deq[s] == i-k+1:
                s += 1
    return res

s_min = slide_min(n, k, p)
s_max = slide_max(n, k, p)

ans = 1
for i in range(n-k):
    if p[i] > s_min[i] or p[i+k] != s_max[i+1]:
        ans += 1

mode = 0
count = 0
e = 0
for i in range(n-1):
    if p[i] < p[i+1]:
        if mode == 0:
            count = 2
            mode = 1
        else:
            count += 1
    else:
        mode = 0
        if count >= k:
            e += 1

if e > 1:
    ans -= e-1

print(ans)

Submission status: Wrong Answer

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

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

def slide_min(n, k, p):
    res = [0] * n
    deq = [0] * n
    s = 0
    t = 0
    for i in range(n):
        while s < t:
            if p[deq[t-1]] >= p[i]:
                t -= 1
            else:
                break
        deq[t] = i
        t += 1
        if i-k+1 >= 0:
            res[i-k+1] = p[deq[s]]
            if deq[s] == i-k+1:
                s += 1
    return res

def slide_max(n, k, p):
    res = [0] * n
    deq = [0] * n
    s = 0
    t = 0
    for i in range(n):
        while s < t:
            if p[deq[t-1]] < p[i]:
                t -= 1
            else:
                break
        deq[t] = i
        t += 1
        if i-k+1 >= 0:
            res[i-k+1] = p[deq[s]]
            if deq[s] == i-k+1:
                s += 1
    return res

s_min = slide_min(n, k, p)
s_max = slide_max(n, k, p)
#print(s_min)
#print(s_max)

ans = 1
for i in range(n-k):
    #print(i, p[i], s_min[i], p[i + k], s_max[i + 1])
    if p[i] > s_min[i] or p[i+k] != s_max[i+1]:
        ans += 1
   # else:
        #print(i, p[i], s_min[i], p[i+k], s_max[i+1])

print(ans)