Problem:


Score : 700 points

Problem Statement

Snuke has a permutation (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1).

Now, he will perform the following operation exactly once:

Choose K consecutive elements in P and sort them in ascending order.

Find the number of permutations that can be produced as P after the operation.

Constraints

2 \leq N \leq 200000

2 \leq K \leq N

0 \leq P_i \leq N-1

P_0,P_1,\cdots,P_{N-1} are all different.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_0 P_1 \cdots P_{N-1}

Output

Print the number of permutations that can be produced as P after the operation.

Sample Input 1

5 3
0 2 1 4 3

Sample Output 1

2

Two permutations can be produced as P after the operation: (0,1,2,4,3) and (0,2,1,3,4).

Sample Input 2

4 4
0 1 2 3

Sample Output 2

1

Sample Input 3

10 4
2 0 1 3 7 5 4 6 8 9

Sample Output 3

6



Sample input:
5 3
0 2 1 4 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
class SegTree:
    """ define what you want to do with 0 index, ex) size = tree_size, func = min or max, sta = default_value """
    
    def __init__(self,size,func,sta):
        self.n = size
        self.size = 1 << size.bit_length()
        self.func = func
        self.sta = sta
        self.tree = [sta]*(2*self.size)

    def build(self, list):
        """ set list and update tree"""
        for i,x in enumerate(list,self.size):
            self.tree[i] = x

        for i in range(self.size-1,0,-1):
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    def set(self,i,x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    
    def get(self,l,r):
        """ take the value of [l r) with func (min or max)"""
        l += self.size
        r += self.size
        res = self.sta

        while l < r:
            if l & 1:
                res = self.func(self.tree[l],res)
                l += 1
            if r & 1:
                res = self.func(self.tree[r-1],res)
            l >>= 1
            r >>= 1
        return res

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

segmin = SegTree(n,min,10**18)
segmax = SegTree(n,max,-1)
segmin.build(p)
segmax.build(p)

count = [1]*n
change = 0
for i in range(1,n):
    if p[i] > p[i-1]:
        count[i] = count[i-1]+1
    else:
        change += 1
if n == k or max(count) == n:
    print(1)
    exit()
if change == 1:
    print(2)
    exit()
ans = n-k+1
if max(count) >= k:
    ans += 1
for i in range(k,n):
    if count[i] >= k:
        ans -= 1
        continue
    if segmin.get(i-k,i+1) == p[i-k] and segmax.get(i-k,i+1) == p[i]:
        ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
class SegTree:
    """ define what you want to do with 0 index, ex) size = tree_size, func = min or max, sta = default_value """
    
    def __init__(self,size,func,sta):
        self.n = size
        self.size = 1 << size.bit_length()
        self.func = func
        self.sta = sta
        self.tree = [sta]*(2*self.size)

    def build(self, list):
        """ set list and update tree"""
        for i,x in enumerate(list,self.size):
            self.tree[i] = x

        for i in range(self.size-1,0,-1):
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    def set(self,i,x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    
    def get(self,l,r):
        """ take the value of [l r) with func (min or max)"""
        l += self.size
        r += self.size
        res = self.sta

        while l < r:
            if l & 1:
                res = self.func(self.tree[l],res)
                l += 1
            if r & 1:
                res = self.func(self.tree[r-1],res)
            l >>= 1
            r >>= 1
        return res

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

segmin = SegTree(n,min,10**18)
segmax = SegTree(n,max,-1)
segmin.build(p)
segmax.build(p)

count = [1]*n
for i in range(1,n):
    if p[i] > p[i-1]:
        count[i] = count[i-1]+1
if n == k or max(count) == n:
    print(1)
    exit()
ans = n-k+1
if max(count) >= k:
    ans += 1
for i in range(k,n):
    if count[i] >= k:
        ans -= 1
        continue
    if segmin.get(i-k,i+1) == p[i-k] and segmax.get(i-k,i+1) == p[i]:
        ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
class SegTree:
    """ define what you want to do with 0 index, ex) size = tree_size, func = min or max, sta = default_value """
    
    def __init__(self,size,func,sta):
        self.n = size
        self.size = 1 << size.bit_length()
        self.func = func
        self.sta = sta
        self.tree = [sta]*(2*self.size)

    def build(self, list):
        """ set list and update tree"""
        for i,x in enumerate(list,self.size):
            self.tree[i] = x

        for i in range(self.size-1,0,-1):
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    def set(self,i,x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    
    def get(self,l,r):
        """ take the value of [l r) with func (min or max)"""
        l += self.size
        r += self.size
        res = self.sta

        while l < r:
            if l & 1:
                res = self.func(self.tree[l],res)
                l += 1
            if r & 1:
                res = self.func(self.tree[r-1],res)
            l >>= 1
            r >>= 1
        return res

n,k = map(int,input().split())
p = list(map(int,input().split()))
if n == k:
    print(1)
    exit()
segmin = SegTree(n,min,10**18)
segmax = SegTree(n,max,-1)
segmin.build(p)
segmax.build(p)

count = [1]*n
for i in range(1,n):
    if p[i] > p[i-1]:
        count[i] = count[i-1]+1

ans = n-k+1
if max(count) >= k:
    ans += 1
for i in range(k,n):
    if count[i] >= k:
        ans -= 1
        continue
    if segmin.get(i-k,i+1) == p[i-k] and segmax.get(i-k,i+1) == p[i]:
        ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
class SegTree:
    """ define what you want to do with 0 index, ex) size = tree_size, func = min or max, sta = default_value """
    
    def __init__(self,size,func,sta):
        self.n = size
        self.size = 1 << size.bit_length()
        self.func = func
        self.sta = sta
        self.tree = [sta]*(2*self.size)

    def build(self, list):
        """ set list and update tree"""
        for i,x in enumerate(list,self.size):
            self.tree[i] = x

        for i in range(self.size-1,0,-1):
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    def set(self,i,x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    
    def get(self,l,r):
        """ take the value of [l r) with func (min or max)"""
        l += self.size
        r += self.size
        res = self.sta

        while l < r:
            if l & 1:
                res = self.func(self.tree[l],res)
                l += 1
            if r & 1:
                res = self.func(self.tree[r-1],res)
            l >>= 1
            r >>= 1
        return res

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

segmin = SegTree(n,min,10**18)
segmax = SegTree(n,max,-1)
segmin.build(p)
segmax.build(p)

count = [1]*n
for i in range(1,n):
    if p[i] > p[i-1]:
        count[i] = count[i-1]+1

ans = n-k+1
if max(count) >= k:
    ans += 1
for i in range(k,n):
    if count[i] >= k:
        ans -= 1
        continue
    if segmin.get(i-k,i+1) == p[i-k] and segmax.get(i-k,i+1) == p[i]:
        ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N, K = MAP()
P = LIST()

check = [0]*(N-K+1)
up_check = [0]*N
for i in range(1, N):
	if P[i] >= P[i-1]:
		up_check[i] = 1

up_check_acc = list(accumulate(up_check))
for i in range(N-K+1):
	if up_check_acc[i+K-1]-up_check_acc[i] == K-1:
		check[i] = 1

q1 = sorted((P[:K]))
q2 = [N]
q3 = sorted([-x for x in P[:K]])
q4 = [N]

ans = N-K+1
for i, p in enumerate(P[K:]):
	heappush(q1, p)
	heappush(q3, -p)
	while q1[0] == q2[0]:
		heappop(q1)
		heappop(q2)

	while q3[0] == q4[0]:
		heappop(q3)
		heappop(q4)

	if q1[0] == P[i] and q3[0] == -p and check[i]*check[i+1] == 0:
		ans -= 1

	heappush(q2, P[i])
	heappush(q4, -P[i])

cnt_up = sum(check)
ans -= cnt_up*(cnt_up-1)//2

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
Ps = list(mapint())

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

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

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

if N==K:
    if tuple(sorted(Ps))==tuple(Ps):
        print(1)
    else:
        print(2)
    exit()
seg_min = SegTree(Ps, segfunc, 10**18)
seg_max = SegTree(Ps, segfunc_2, -1)

str_set = set()
cnt = 1
old = 10**18
is_increase = [0]*N
for i in range(N):
    p = Ps[i]
    if p>old:
        cnt += 1
        is_increase[i] = cnt
    else:
        cnt = 1
        is_increase[i] = cnt
    old = p

original = 0
ans = N-K+1
for i in range(N-K):
    mini = Ps[i]
    maxi = Ps[i+K]
    if is_increase[i+K-1]>=K:
        original = 1
        ans -= 1
    elif (seg_min.query(i, i+K+1)==mini and seg_max.query(i, i+K+1)==maxi):
        ans -= 1
if is_increase[-1]>=K:
    original = 1
    ans -= 1
print(ans+original)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
Ps = list(mapint())

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

def segfunc_2(x, y):
    return max(x, y)
ide_ele = 10**18

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

if N==K:
    if tuple(sorted(Ps))==tuple(Ps):
        print(1)
    else:
        print(2)
    exit()
seg_min = SegTree(Ps, segfunc, ide_ele)
seg_max = SegTree(Ps, segfunc_2, -1)
ans = N-K+1
str_set = set()

cnt = 1
old = 10**18
is_increase = [0]*N
for i in range(N):
    p = Ps[i]
    if p>old:
        cnt += 1
        is_increase[i] = cnt
    else:
        cnt = 1
        is_increase[i] = cnt
    old = p
original = 0
for i in range(N-K):
    mini = Ps[i]
    maxi = Ps[i+K]
    if is_increase[i+K-1]>=K:
        original = 1
        ans -= 1
    elif (seg_min.query(i, i+K+1)==mini and seg_max.query(i, i+K+1)==maxi):
        ans -= 1
if is_increase[-2]<K and is_increase[-1]>=K:
    original = 1
    ans -= 1
print(ans+original)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
Ps = list(mapint())

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

def segfunc_2(x, y):
    return max(x, y)
ide_ele = 10**18

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

if N==K:
    if tuple(sorted(Ps))==tuple(Ps):
        print(1)
    else:
        print(2)
    exit()
seg_min = SegTree(Ps, segfunc, ide_ele)
seg_max = SegTree(Ps, segfunc_2, -1)
ans = N-K+1
str_set = set()

cnt = 1
old = 10**18
is_increase = [0]*N
for i in range(N):
    p = Ps[i]
    if p>old:
        cnt += 1
        is_increase[i] = cnt
    else:
        cnt = 1
        is_increase[i] = cnt
    old = p
original = 0
for i in range(N-K):
    mini = Ps[i]
    maxi = Ps[i+K]
    if is_increase[i+K-1]>=K:
        original = 1
        ans -= 1
    elif (seg_min.query(i, i+K+1)==mini and seg_max.query(i, i+K+1)==maxi):
        ans -= 1
if is_increase[-1]>=K:
    original = 1
    ans -= 1
print(ans+original)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
Ps = list(mapint())

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

def segfunc_2(x, y):
    return max(x, y)
ide_ele = 10**18

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

if N==K:
    if tuple(sorted(Ps))==tuple(Ps):
        print(1)
    else:
        print(2)
    exit()
seg_min = SegTree(Ps, segfunc, ide_ele)
seg_max = SegTree(Ps, segfunc_2, -1)
ans = (N-K+1)

str_set = set()
for i in range(N-K):
    mini = Ps[i]
    maxi = Ps[i+K-1]
    if seg_min.query(i, i+K)==mini and seg_max.query(i, i+K)==maxi:
        ans -= 1
print(ans)

Submission status: Wrong Answer

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

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

bit = Bit(n+1)
ans = 0
 
for i, p in enumerate(ppp):
    bit.add(p+1, 1)
    ans += i + 1 - bit.sum(p+1)
 
print(max(ans,1))

Submission status: Wrong Answer

Solution code:
def segfunc_min(x,y):return min(x,y)
def segfunc_max(x,y):return max(x,y)
ide_ele_min=10**18
ide_ele_max=0
class segtree():
  def __init__(self,init_val,segfunc,ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,k=map(int,input().split())
*p,=map(int,input().split())
q=[1]*n
ans=n-k+1
cnt=1
c=0
for i in range(n-1):
  if p[i+1]>p[i]:cnt+=1
  else:cnt=1
  c+=cnt>=k
  if cnt>k:q[i-k]=0
if c>1:ans-=c-1
stn=segtree(p,segfunc_min,ide_ele_min)
stx=segtree(p,segfunc_max,ide_ele_max)
for i in range(n-k):
  if stn.query(i,i+k)==p[i] and stx.query(i+1,i+k+1)==p[i+k] and q[i]:ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
def segfunc_min(x,y):return min(x,y)
def segfunc_max(x,y):return max(x,y)
ide_ele_min=10**18
ide_ele_max=0
class segtree():
  def __init__(self,init_val,segfunc,ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,k=map(int,input().split())
*p,=map(int,input().split())
ans=n-k+1
stn=segtree(p,segfunc_min,ide_ele_min)
stx=segtree(p,segfunc_max,ide_ele_max)
for i in range(n-k):
  if stn.query(i,i+k)==p[i] and stx.query(i+1,i+k+1)==p[i+k]:ans-=1
cnt=1
c=0
for i in range(n-1):
  if p[i+1]>p[i]:cnt+=1
  else:cnt=1
  c+=cnt>=k
if c>1:ans-=c-1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq


def get_asc_flags(N, K, P):
    diff_flags = [0] * (N - 1)  # 増：1、減：-1、プラスマイナス0：0
    for i in range(N - 1):
        if P[i] < P[i + 1]:
            diff_flags[i] = 1
        elif P[i] > P[i + 1]:
            diff_flags[i] = - 1
    # 所望の部分の特定
    asc_flags = [0] * (N - K + 1)
    diff_sums = sum(diff_flags[:(K - 2)])
    for i in range(N - K + 1):
        diff_sums += diff_flags[i + K - 2]
        if diff_sums == K - 1:
            asc_flags[i] = 1
        diff_sums -= diff_flags[i]
    return asc_flags


def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    # K個連続で昇順で並んでいる部分の特定
    # asc_flags[i] == 1 → i番目からK個の間は昇順で並んでいる
    asc_flags = get_asc_flags(N, K, P)
    # 基本はN - K + 1通り。その中での重複を考える。
    kinds = [i for i in range(N - K + 1)]  # 最終的な答えばlen(set(kinds))
    checked = [0] * N
    checked[P[0]] = 1
    min_que, max_que = [], []
    for i in range(1, K):
        heapq.heappush(min_que, P[i])
        heapq.heappush(max_que, - P[i])
    for i in range(N - K + 1):
        # (1) 選択された列がすでに昇順になっているケース
        if asc_flags[i] == 1:
            kinds[i] = -1
            continue
        # (2) i-1番目が先頭の列とi番目が先頭の列を比較する。
        # この2つが一致するのは下記の2条件が両方成り立つ時：
        #   i-1番目の列を昇順に並べても先頭は不変
        #   i番目の列を昇順に並べても最後尾は不変
        if i == 0:
            continue
        old_p, new_p = P[i - 1], P[i + K - 1]
        while checked[min_que[0]] == 1:
            heapq.heappop(min_que)
        while checked[-max_que[0]] == 1:
            heapq.heappop(max_que)
        if old_p < min_que[0] and new_p > - max_que[0]:
            kinds[i] = kinds[i - 1]
        heapq.heappush(min_que, new_p)
        heapq.heappush(max_que, - new_p)
        checked[P[i]] = 1
    print(len(set(kinds)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
l,r=0,K-1
ans=1
for i in range(N-K):
  if A[l]<A[l+1] and A[r]<A[r+1]:
    r+=1
    l+=1
  else:
    ans+=1
    r+=1
    l+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, left, right):
        """
        [left, right)のsegfuncしたものを得る
        left: index(0-index)
        right: index(0-index)
        """
        res = self.ide_ele
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segfunc(res, self.tree[left])
                left += 1
            if right & 1:
                res = self.segfunc(res, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return res


def resolve():
    n, k = map(int, input().split())
    P = list(map(int, input().split()))

    seg_min = SegTree(P, lambda x, y: min(x, y), f_inf)
    seg_max = SegTree(P, lambda x, y: max(x, y), -f_inf)
    mi = seg_min.query(0, k)
    ma = seg_max.query(0, k)
    res = 1
    for i in range(1, n - k + 1):
        prev = P[i - 1]
        new = P[i + k - 1]
        if prev != mi or new < ma:
            res += 1
        mi = seg_min.query(i, i + k)
        ma = seg_max.query(i, i + k)

    cnt = 1
    t = 0
    for i in range(1, n):
        if P[i - 1] < P[i]:
            cnt += 1
        if cnt == k:
            t += 1
            cnt = 1
    print(res - max(0, (t - 1)))


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
class SegmentTree:

    def __init__(self, n, op, e):
        """
        :param n: 要素数
        :param op: 二項演算
        :param e: 単位減
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 1 << (self.n - 1).bit_length()      # st[self.size + i] = array[i]
        self.tree = [self.e] * (self.size << 1)

    def built(self, array):
        """arrayを初期値とするセグメント木を構築"""
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """i 番目の要素を x に更新　(0-indexed) """
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def get(self, l, r):
        """ [l, r)の区間取得の結果を返す　(0-indexed) """
        l += self.size
        r += self.size
        res_l = self.e
        res_r = self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.tree[r], res_r)
            l >>= 1
            r >>= 1
        return self.op(res_l, res_r)

    def __iter__(self):
        for a in self.tree[self.size:self.size+self.n]:
            yield a

    def __str__(self):
        return str(self.tree[self.size:self.size+self.n])

##################################################################################################################
import sys
input = sys.stdin.readline


N, K = map(int, input().split())
P = list(map(int, input().split()))
e = float("inf")
op = lambda x, y : x if x < y else y
st1 = SegmentTree(N, op, e)
st1.built(P)
e = 0
op = lambda x, y : x if x > y else y
st2 = SegmentTree(N, op, e)
st2.built(P)

Q = [1]
for i in range(N-1):
    if P[i] < P[i+1]:
        Q.append(Q[-1]+1)
    else:
        Q.append(1)

res, flg = 1, 0
for i in range(1,N-K+1):
    mi, ma = st1.get(i,i+K-1), st2.get(i,i+K-1)
    if (P[i+K-1] < ma or P[i-1] > mi):
        if Q[i+K-1]<K:
            res += 1
        elif not flg:
            res += 1
            flg = 1
print(res)

Submission status: Wrong Answer

Solution code:
class SegmentTree:
    """
    演算子は要素とセットでモノイドを形成するようなものでなければならない。
    すなわち、結合律が成り立ち単位元が存在する必要がある。(ただし単位元は添加可能)
    """
    @classmethod
    def all_identity(cls, operator, identity, size):
        return cls(operator, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator, identity, data):
        self.op = operator
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        while i:
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return iter(self.data[self.size:])

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

def solve(K,P):
    N = len(P)
    maxseg = SegmentTree.from_initial_data(max2, -1, P)
    minseg = SegmentTree.from_initial_data(min2, N, P)

    delta = [b-a for a,b in zip(P,P[1:])]
    deltaseg = SegmentTree.from_initial_data(min2, N, delta)

    c = 1
    for i in range(N-K):
        a = maxseg[i+1:i+K]
        b = minseg[i+1:i+K]
        c += int(b < P[i] or a > P[i+K])

    d = 0
    for i in range(N-K+1):
        x = deltaseg[i:i+K-1]
        if x > 0:
            d += 1
    d = max2(0,d-1)
    return c - d

if __name__ == '__main__':
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    print(solve(K,P))