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 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
    

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()))
count = n-(k-1)

m = p[0]
for i in range(1, n-k):
    if p[i-1] == m and max(p[i:i+k]) == p[i+k-1]:
        count -= 1
    m = min(p[i:i+k])
print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf8 -*-

n,k = map(int, input().split())
p = list(map(int, input().split()))
ans = 1
b = sorted(p[0:k])
for i in range(1,n - k):
    c = sorted(p[i:i+k])
    if b != c:
        ans += 1
        b = c
print(ans)

Submission status: Wrong Answer

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

count = 1
for i in range(N - K + 1):
		if i == 0:
				tmp = sorted(P[0:K] , reverse=False)
				Kmax = tmp[K-1]
				Kmin = tmp[0]

		else:
				if Kmax == P[i-1]:
						tmp = sorted(P[i:i+K], reverse=False)
						Kmax = tmp[0]
						Kmin = tmp[K - 1]
						count += 1

						continue
				elif Kmin == P[i-1]:
						if Kmax < P[i+K-1]:
								Kmax = P[i+K]
								continue
						else:
								tmp = sorted(P[i:i + K], reverse=False)
								Kmax = tmp[0]
								Kmin = tmp[K - 1]
								count += 1
								continue
				Kmax = max(Kmax, P[i+K-1])
				Kmin = max(Kmin, P[i+K-1])
				if i == N-K:
						tmp = sorted(P[i:i + K], reverse=False)
						if tmp != P[i:i+K]:
								count += 1
						continue
				count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import unittest
import collections


def solve(n, k, ps):
    if n == k:
        return 1

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

    min_dq = collections.deque()
    max_dq = collections.deque()
    min_dq.append(0)
    max_dq.append(0)
    for i in range(1, k-1):
        if min_dq[0] < i-k+1:
            min_dq.popleft()
        while min_dq and ps[min_dq[-1]] >= ps[i]:
            min_dq.pop()
        min_dq.append(i)
        if max_dq[0] < i-k+1:
            max_dq.popleft()
        while max_dq and ps[max_dq[-1]] <= ps[i]:
            max_dq.pop()
        max_dq.append(i)
    pre_min = min_dq[0]
    pre_max = max_dq[0]

    cnt = 0
    has_zero = False
    for i in range(k - 1, n):
        pre_min = ps[min_dq[0]]
        pre_max = ps[max_dq[0]]
        if min_dq[0] < i-k+1:
            min_dq.popleft()
        while min_dq and ps[min_dq[-1]] >= ps[i]:
            min_dq.pop()
        min_dq.append(i)
        if max_dq[0] < i-k+1:
            max_dq.popleft()
        while max_dq and ps[max_dq[-1]] <= ps[i]:
            max_dq.pop()
        max_dq.append(i)

        if valid[i] != 0:
            if cnt == 0:
                cnt += 1
                continue
            if cnt == 0 or valid[i - 1] != valid[i] or (pre_max != ps[i - 1] and ps[min_dq[0]] != ps[i - k + 1]) or (pre_min != ps[i - k] and ps[max_dq[0]] != ps[i]):
                if pre_min == ps[i - k] and max_dq[0] == i:
                    continue
                cnt += 1
        else:
            has_zero = True
    if has_zero:
        cnt += 1
    return cnt


def main():
    n, k = map(int, input().split())
    ps = list(map(int, input().split()))
    print(solve(n, k, ps))


class TestAcd038B(unittest.TestCase):
    def test_agc038b(self):
        self.assertEqual(solve(5, 3, list(map(int, '0 2 1 4 3'.split()))), 2)
        self.assertEqual(solve(4, 4, list(map(int, '0 1 2 3'.split()))), 1)
        self.assertEqual(
            solve(10, 4, list(map(int, '2 0 1 3 7 5 4 6 8 9'.split()))), 6)
        self.assertEqual(
            solve(10, 2, list(map(int, '1 2 3 4 5 6 7 8 9 0'.split()))), 2)
        self.assertEqual(
            solve(10, 4, list(map(int, '0 1 2 4 3 5 6 8 7 9'.split()))), 3)


if __name__ == "__main__":
    main()
    # unittest.main()

Submission status: Wrong Answer

Solution code:
import unittest
import collections


def solve(n, k, ps):
    if n == k:
        return 1

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

    min_dq = collections.deque()
    max_dq = collections.deque()
    min_dq.append(0)
    max_dq.append(0)
    for i in range(1, k-1):
        if min_dq[0] < i-k+1:
            min_dq.popleft()
        while min_dq and ps[min_dq[-1]] >= ps[i]:
            min_dq.pop()
        min_dq.append(i)
        if max_dq[0] < i-k+1:
            max_dq.popleft()
        while max_dq and ps[max_dq[-1]] <= ps[i]:
            max_dq.pop()
        max_dq.append(i)
    pre_min = min_dq[0]
    pre_max = max_dq[0]

    cnt = 0
    has_zero = False
    for i in range(k - 1, n):
        pre_min = ps[min_dq[0]]
        pre_max = ps[max_dq[0]]
        if min_dq[0] < i-k+1:
            min_dq.popleft()
        while min_dq and ps[min_dq[-1]] >= ps[i]:
            min_dq.pop()
        min_dq.append(i)
        if max_dq[0] < i-k+1:
            max_dq.popleft()
        while max_dq and ps[max_dq[-1]] <= ps[i]:
            max_dq.pop()
        max_dq.append(i)

        if valid[i] != 0:
            if cnt == 0:
                cnt += 1
                continue
            if cnt == 0 or valid[i - 1] != valid[i] or (pre_max != ps[i - 1] and ps[min_dq[0]] != ps[i - k + 1]) or (pre_min != ps[i - k] and ps[max_dq[0]] != ps[i]):
                if pre_min == ps[i - k] and max_dq[0] == i:
                    continue
                cnt += 1
        else:
            has_zero = True
    if has_zero:
        cnt += 1
    return cnt


def main():
    n, k = map(int, input().split())
    ps = list(map(int, input().split()))
    print(solve(n, k, ps))


class TestAcd038B(unittest.TestCase):
    def test_agc038b(self):
        self.assertEqual(solve(5, 3, list(map(int, '0 2 1 4 3'.split()))), 2)
        self.assertEqual(solve(4, 4, list(map(int, '0 1 2 3'.split()))), 1)
        self.assertEqual(
            solve(10, 4, list(map(int, '2 0 1 3 7 5 4 6 8 9'.split()))), 6)
        self.assertEqual(
            solve(10, 2, list(map(int, '1 2 3 4 5 6 7 8 9 0'.split()))), 2)
        self.assertEqual(
            solve(10, 4, list(map(int, '0 1 2 4 3 5 6 8 7 9'.split()))), 3)


if __name__ == "__main__":
    # main()
    unittest.main()

Submission status: Wrong Answer

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

ch = P[0]
block = 1
ren = 1
bl = []
for n in range(1, N):
  if P[n] != (ch + 1):
    block += 1
    bl.append(ren)
    ren = 1
  else:
    ren += 1
  ch = P[n]
  
bl.append(ren)  

cnt = 0
for b in bl:
  if b > K:
    cnt += (b- (K-1)-1)
print(N - (K - 1) - cnt - 1)

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):
            min_list[i] = 1

    for i in range(n - k):
        if p_list[i + k - 1] == max_tree.query(i, i + k):
            max_list[i + k - 1] = 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:
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


n, k = map(int, input().split())
p = tuple(int(x) for x in input().split())
segfunc = min
#####単位元######
ide_ele = 200000 + 10

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

ans = n - k + 1
# ここから減らす

val_min = [0] * n
val_max = [0] * n

sorted_count = 0

cont = 0
i = 0
while i < n:
    if query(i, min(i + k, n)) == p[i]:
        cont += 1
        if cont == k:
            sorted_count += 1
    else:
        cont = 0
    val_min[i] = cont
    if cont == k:
        i += k - 1
    i += 1

segfunc = max
ide_ele = -1
seg = [ide_ele] * 2 * num
init(p)

cont = 0
for i in range(n - 1, -1, -1):
    if query(max(0, i - k + 1), i + 1) == p[i]:
        cont += 1
    else:
        cont = 0
    val_max[i] = cont

if sorted_count > 0:
    ans -= sorted_count - 1

cont = 0
for i in range(n - k):
    if val_min[i] is not 0 and val_max[i + k] is not 0:
        ans -= 1

print(ans)
#
# print(val_min)
# print(val_max)

Submission status: Wrong Answer

Solution code:
import copy

N,K = list(map(int, input().split()))
P = list(map(int, input().split()))
A = [[]] * (N-K+1)

for i in range(N-K+1):
    A[i] = copy.deepcopy(P)
    A[i][i : i+K] = sorted(A[i][i : i+K])

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]


print(len(A))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
f = list(sorted(p[:k]))
min_, max_ = f[0], f[-1]
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_)
print(ans)

Submission status: Wrong Answer

Solution code:
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


n, k = map(int, input().split())
p = tuple(int(x) for x in input().split())
segfunc = min
#####単位元######
ide_ele = 200000 + 10

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

ans = n - k + 1
# ここから減らす

val_min = [0] * n
val_max = [0] * n

sorted_count = 0

cont = 0
i = 0
while i < n:
    if query(i, min(i + k, n)) == p[i]:
        cont += 1
        if cont == k:
            sorted_count += 1
    else:
        cont = 0
    val_min[i] = cont
    if cont == k:
        i += k - 1
    i += 1

segfunc = max
ide_ele = -1
seg = [ide_ele] * 2 * num
init(p)

cont = 0
for i in range(n - 1, -1, -1):
    if query(max(0, i - k + 1), i + 1) == p[i]:
        cont += 1
    else:
        cont = 0
    val_max[i] = cont

if sorted_count > 0:
    ans -= sorted_count - 1

cont = 0
for i in range(n - k):
    if val_min[i] is not 0 and val_max[i + k] is not 0:
        ans -= 1

if ans == 0:
    print(1)
else:
    print(ans)
#
# print(val_min)
# print(val_max)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
inf=10**8
cnt=1

p=[-inf]+p+[inf]
f=0
for i in range(1,n-k+2):
  if p[i:i+k]==sorted(p[i:i+k]):
    f=1
  else:
    if min(p[i:i+k])>p[i-1] and max(p[i:i+k])<p[i+k] and f==0:
      f=1
      cnt+=1
    else:
      f=0
      cnt+=1
print(cnt)

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:
N,K = map(int,input().split())
P = list(map(int,input().split()))

asc_cum = [0]
for p,q in zip(P,P[1:]):
    asc_cum.append(asc_cum[-1] + int(p<q))

all_asc = []
for i in range(K-1,N):
    all_asc.append(asc_cum[i] - asc_cum[i-K+1] == K-1)

import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

    def size(self):
        return len(self.hq)

q_asc = Heapq([], True)
q_desc = Heapq([])

mins = []
maxs = []
for k in range(K-1):
    q_asc.push(P[k])
    q_desc.push(P[k])
for k in range(N-K+1):
    mins.append(q_desc.pop())
    maxs.append(q_asc.pop())
    q_asc.push(k+K-1)
    q_desc.push(k+K-1)

first_asc = False
ans = 0
for i,asc in enumerate(all_asc):
    if not asc:
        if i>0:
            #print(i,segt_min.query(i,i+K-1),segt_max.query(i,i+K-1))
            #if min(P[i:i+K-1]) > P[i-1] and max(P[i:i+K-1]) < P[i+K-1]:
            #if segt_min.query(i,i+K-1) > P[i-1] and segt_max.query(i,i+K-1) < P[i+K-1]:
            if mins[i] > P[i-1] and maxs[i] < P[i+K-1]:
                continue
        ans += 1
        continue
    if not first_asc:
        first_asc = True
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

N,K = list(map(int, input().split()))
P = list(map(int, input().split()))
A = [[]] * (N-K+1)

print(A)
for i in range(N-K+1):
    A[i] = copy.deepcopy(P)
    A[i][i : i+K] = sorted(A[i][i : i+K])

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

print(get_unique_list(A))

print(len(A))

Submission status: Wrong Answer

Solution code:
import heapq as hq
n,k = map(int,input().split())
p = list(map(int,input().split()))
t_max = max(p[:k])
t_min = min(p[:k])
cnt = 0
q = p[:k].copy()
hq.heapify(q)
for i in range(n-k):
    cnt += 1
    if t_max < p[i + k] and t_min == p[i]:
        cnt -= 1
        t_max = p[i + k]
        hq.heappop(q)
        hq.heappush(q,p[i+k])
        t_min = q[0]
print(cnt + 1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
class Min_seg:
    def __init__(self,n,init_val,ide_ele = 10**9):
        # set_val
        self.ide_ele = ide_ele #単位元
        self.n = n #要素数
        self.num = 2 ** (self.n - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]
            # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = min(self.seg[2 * i + 1], self.seg[2 * i + 2])
    def update(self,k, x):
        k += self.num - 1
        self.seg[k] = x
        while k + 1:
            k = (k - 1) // 2
            self.seg[k] = min(self.seg[k * 2 + 1], self.seg[k * 2 + 2])


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

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


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

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

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

#print(ans,"試し")

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

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


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

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

heap_min = []
heap_max = []
cnt = 0
not_changed = False
for i in range(K):
    heapq.heappush(heap_min,P[i])
    heapq.heappush(heap_max,P[i]*(-1))
    if i != 0 and P[i-1] < P[i]:
        cnt += 1
        if cnt == K-1:
            not_changed = True
    else:
        cnt = 0



total = 1
alreadyremoved = {}

for i in range(K,N):
    if not (heap_min[0] == P[i-K] and heap_max[0]*(-1) < P[i]):
        if not_changed:
            if cnt < K-1:
                total += 1
        else:
            total += 1
    if P[i-1] < P[i]:
        cnt += 1
        if cnt == K-1:
            not_changed = True
    else:
        cnt = 0

    alreadyremoved[P[i-K]] = True
    heapq.heappush(heap_min,P[i])
    heapq.heappush(heap_max,P[i]*(-1))
    
    while heap_min[0] in alreadyremoved:
        heapq.heappop(heap_min)
    while heap_max[0]*(-1) in alreadyremoved:
        heapq.heappop(heap_max)

    
print(total)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
if N == K:
    print(1)
    exit()
P = list(map(int,input().split()))
s = sorted(range(len(P)), key=lambda k: P[k])
P = sorted(range(len(s)), key=lambda k: s[k])
count=1

m = min(P[ : K])
M = max(P[ : K])
for i in range(N-K+1):
    if m == P[i] and M < P[i+K+1]:
        M = P[i+K+1]
        m = min(P[i : i+K])
        continue
    else:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
P=[int(i) for i in input().split()]
import collections
from collections import deque
M1,M2=deque(),deque()
A1,A2=[],[]
M1.append(P[0])
for i in range(1,n):
  
  while M1:
    if P[M1[-1]]>P[i]:
      M1.pop()
    else:
      M1.append(i)
      break
  if not M1:
    M1.append(i)
  if M1[0]==i-k-1:
    M1.popleft()
  A1.append(P[M1[0]])
M2.append(P[0])
for i in range(1,n):
  
  while M2:
    if P[M2[-1]]<P[i]:
      M2.pop()
    else:
      M2.append(i)
      break
  if not M2:
    M2.append(i)
  if M2[0]==i-k-1:
    M2.popleft()
  A2.append(P[M2[0]])
ans=1
for i in range(n-k):
  if A1[-(k-1+i)]==P[i] and A2[-(k-1+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:
a=[]
b=[]
c=[]
cm=[]
i=0
n=0
for x in input().split(" "):
    b.append(int(x))
for x in input().split(" "):
    a.append(int(x))

while i<b[0]-b[1]:
    c = a[i : i+b[1]]
    c.sort
    if c[-1] == a[i+b[1]] :
        i+=2
    else:
        i+=1
    n+=1
    cm=[]
    c=[]
print(n)

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
for l in range(n - k):
    if L[l] > L[l + 1] or L[l + k - 1] > L[l + k] and sorted(L[l + 1: l + k]) != L[l + 1: l + k]:
        cnt += 1


print(cnt)

Submission status: Wrong Answer

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

chant_sort = 0

for i in range(N-K+1):
  if A[i:i+K] == sorted(A[i:i+K]):
    chant_sort += 1

print(sorted(A[0:1+K]))
print(A[1:1+K])
    
ans = N - K + 1 - chant_sort

print(ans)

Submission status: Wrong Answer

Solution code:
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


n, k = map(int, input().split())
p = tuple(int(x) for x in input().split())
segfunc = min
#####単位元######
ide_ele = 200000 + 10

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

ans = n - k + 1
# ここから減らす

val_min = [0] * n
val_max = [0] * n

sorted_count = 0

cont = 0
i = 0
while i < n:
    if query(i, min(i + k, n)) == p[i]:
        cont += 1
        if cont == k:
            sorted_count += 1
    else:
        cont = 0
    val_min[i] = cont
    if cont == k:
        i += k - 1
    i += 1

segfunc = max
ide_ele = -1
seg = [ide_ele] * 2 * num
init(p)

cont = 0
for i in range(n - 1, -1, -1):
    if query(max(0, i - k + 1), i + 1) == p[i]:
        cont += 1
    else:
        cont = 0
    val_max[i] = cont

if sorted_count > 0:
    ans -= sorted_count

cont = 0
for i in range(n - k):
    if val_min[i] is not 0 and val_max[i + k] is not 0:
        ans -= 1

if ans == 0:
    print(1)
else:
    print(ans)
#
# print(val_min)
# print(val_max)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = [int(i) for i in input().split()]
ans = N-K+1
s = []
for i in range(N-K-1):
    for j in range(i, i+K+1):
        s.append(P[j])
        if P[i] == min(s) and P[i+K] == max(s):
            ans -= 1
    s = []
    
for i in range(N-K):
    for j in range(i, i+K-1):
        if P[j+1] < P[j]:
            break
    else:
        ans -= 1
        
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
A = []
a = min(P[0:K-1])
b = max(P[:K-1])
A.append((a,b))
for i in range(1,N-K+1):
    if P[i+K-1]>b:
        b = P[i-K+1]
    if P[i-1]<a:
        a = P[i-1]
    A.append((a,b))
B = {}
cur = 0
for i in range(1,N):
    if P[i]<P[i-1]:
        if i-cur>=K:
            B[cur] = i-cur
        cur = i
if N-cur>=K:
    B[cur] = N-cur
d = 0
if len(B)>1:
    d = len(B)-1
cnt = 1
for i in range(K,N):
    if P[i]<A[i-K][1] or P[i-K]>A[i-K][0]:
        cnt += 1
print(cnt-d)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

count=n-k+1
first=0
pp=p[0:k]
pp_s=np.sort(pp)

for i in range(len(pp)):
    if pp_s[i]!=pp[i]:
        for i in range(len(pp)-1):
            if pp[k-1-i]<pp[k-2-i]:
                seq=i+1
                break
        break
    if i==len(pp)-1:
        if first==0:
            first+=1
            seq=k
ma=np.max(pp)
mi=np.min(pp)

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

Submission status: Wrong Answer

Solution code:
import heapq as hq
n,k = map(int,input().split())
p = list(map(int,input().split()))
t_max = max(p[:k])
t_min = min(p[:k])
cnt = 0
q = p[:k].copy()
hq.heapify(q)
for i in range(n-k):
    cnt += 1
    if t_max < p[i + k] and t_min == p[i]:
        cnt -= 1
        t_max = p[i + k]
        hq.heappop(q)
        hq.heappush(q,p[i+k])
print(cnt + 1)