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

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
#print(ans)
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) 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: Accepted

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 + 1):
        if p_list[i] == min_tree.query(i, i + k):
            min_list[i] = 1

    for i in range(n - k + 1):
        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: Accepted

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

import heapq

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

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

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self,param,default,func):
        if isinstance(param,list):
            n=len(param)
        else:
            n=param
        self.d=default
        self.leaf=1<<(n-1).bit_length()
        if isinstance(param,list):
            self.tree=[default]*(self.leaf-1)+param+[default]*(self.leaf-n)
            for i in range(self.leaf-2,-1,-1):
                self.tree[i]=func(self.tree[i*2+1],self.tree[i*2+2])
        else:
            self.tree=[default]*(self.leaf*2-1)
        self.f=func
    def find(self,i):
        return self.tree[i+self.leaf-1]
    def merge(self,a,b):
        return self.f(a,b)
    def get_top(self):
        return self.tree[0]
    def query(self,a,b): #[a,b)
        T=self.tree
        l,r=a+self.leaf-1,b+self.leaf-1
        res=self.d
        while l<r:
            if not l%2:
                res=self.merge(res,T[l])
                l+=1
            if not r%2:
                r-=1
                res=self.merge(res,T[r])
            l>>=1; r>>=1
        return res

def main():
    inf=10**7
    n,k=map(int,input().split())
    P=list(map(int,input().split()))
    segmax=SegmentTree(P,0,max)
    segmin=SegmentTree(P,inf,min)
    ans=n-k+1
    for i in range(n-k):
        if segmin.query(i,i+k)==P[i] and segmax.query(i,i+k)<P[i+k]:
            ans-=1
    tmp=1
    cnt=0
    for i in range(n-1):
        if P[i]>P[i+1]:
            if tmp>=k:
                cnt+=1
            tmp=1
        else:
            tmp+=1
    if tmp>=k:
        cnt+=1
    if cnt:
        ans-=cnt-1
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import math


def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    seq = 1
    for i in range(K-1):
        if P[i] < P[i+1]:
            seq += 1
        else:
            seq = 1
    has_orig = seq == K
    ln = int(math.log(K, 2))
    dp1 = [[0] * N for _ in range(ln+1)]
    dp2 = [[0] * N for _ in range(ln+1)]
    dp1[0] = P
    dp2[0] = P
    for k in range(ln):
        for i in range(N-2**k):
            dp1[k+1][i] = min(dp1[k][i], dp1[k][i+2**k])
            dp2[k+1][i] = max(dp2[k][i], dp2[k][i+2**k])
    rmq = [float("inf")] * (N-K+1)
    rMq = [0] * (N-K+1)
    for i in range(N-K+1):
        idx = i
        for k in range(ln+1)[::-1]:
            if K & (2**k):
                rmq[i] = min(rmq[i], dp1[k][idx])
                rMq[i] = max(rMq[i], dp2[k][idx])
                idx += 2**k
    ans = 1
    for i in range(N-K):
        if P[i+K-1] < P[i+K]:
            seq += 1
        else:
            seq = 1
        if seq >= K:
            if not has_orig:
                has_orig = True
                ans += 1
            continue
        if P[i] != rmq[i] or P[i+K] < rMq[i]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heapify, heappop, heappush
def main():
    N, K = map( int, input().split())
    P = list( map( int, input().split()))
    ans = 0
    now = -1
    cnt = 1
    CNT = [0]*N
    for i in range(N-1,-1,-1):
        p = P[i]
        if p < now:
            cnt += 1
        else:
            cnt = 1
        now = p
        if cnt >= K:
            CNT[i] = 1
    if sum(CNT) > 0:
        ans = 1
            
    for i in range(K-1):
        if P[i] > P[i+1]:
            ans += 1
            break
    Max = [ -P[i] for i in range(K)]
    Min = [ P[i] for i in range(K)]
    heapify(Max)
    heapify(Min)
    C = [0]*N
    for i in range(K, N):
        while C[Min[0]] == 1:
            heappop(Min)
        while C[-Max[0]] == 1 or Max[0] == -P[i-K]:
            heappop(Max)
        # print(C, Max)
        # print(P[i+1-K])
        # print(P[i-K], Min[0], P[i] , -Max[0])
        if CNT[i+1-K] == 1:
            pass
        elif P[i-K] == Min[0] and P[i] > -Max[0]:
            pass
        else:
            ans += 1
        C[P[i-K]] = 1
        heappush(Min, P[i])
        heappush(Max, -P[i])
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx

readline = sys.stdin.readline
N, K = map(int, readline().split())
P = list(map(int, readline().split()))
STmax = Segtree(P, 0, True, max)
STmin = Segtree(P, 10**9, True, min)
ans = N - K + 1
upper = [0]*(N-1)
for i in range(N-1):
    if P[i] > P[i+1]:
        upper[i] = 1
upper = list(accumulate(upper)) + [0]
cnt = 0
for i in range(N-K):
    if upper[i+K-2] == upper[i-1]:
        cnt += 1
    elif P[i+K] == STmax.query(i+1, i+K+1) and P[i] == STmin.query(i, i+K):
        ans -= 1
if upper[N-2] == upper[N-K-1]:
    cnt += 1
print(ans - max(0, cnt-1))

Submission status: Accepted

Solution code:
class segtree():
    def segfunc(x,y):
        return min(x,y)
    #####単位元######
    ide_ele = -1
    n=1
    init_val=[0]*n
    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    
    def __init__(self,INIT_VAL,SEGFUNC,IDE_ELE):
        self.ide_ele=IDE_ELE
        self.init_val=[i for i in INIT_VAL]
        self.segfunc=SEGFUNC
        self.n=len(self.init_val)
        self.num =2**(self.n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num

        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1]=self.init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(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] = self.segfunc(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 = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)

N,K=map(int,input().split())
P=[int(i) for i in input().split()]
mintree=segtree(P,min,N)
maxtree=segtree(P,max,-1)
G=UnionFind(N-K+1)
for i in range(N-K):
    m=mintree.query(i+1,i+K)
    M=maxtree.query(i+1,i+K)
    #print(m,M)
    if P[i]<m and M<P[i+K]:
        G.unite(i,i+1)
aaa=[G.find(i) for i in range(N-K+1)]
Q=[1 for i in range(N)]
for i in range(N-1):
    if P[i]<P[i+1]:
        Q[i+1]=Q[i]+1
    else:
        Q[i+1]=1
tmp=0
for i in range(N):
    if Q[i]==K:
        tmp+=1
if tmp>0:
    tmp-=1
print(len(set(aaa))-tmp)

Submission status: Accepted

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

N0 = 2**(N-1).bit_length()
INF = 2**31-1
data_m = [INF]*(2*N0)
data_M = [INF]*(2*N0)

def update(k, x, data):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

def query(l, r, data):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N):
    update(i, P[i], data_m)
    update(i, -P[i], data_M)

s = [1]*N
r = 0
for l in range(N):
    r = max(l,r)
    while r < N-1:
        if P[r]<P[r+1]:
            r += 1
        else:
            break
    s[l] = r-l+1
    
ans = 0
if s[0]<K:
    ans += 1

for i in range(1,N-K+1):
    if query(i-1,i+K,data_m)!=P[i-1] or query(i-1,i+K,data_M)!=-P[i+K-1]:
        if s[i]<K:
            ans += 1

if max(s) >= K:
    ans += 1

print(ans)

Submission status: Accepted

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

upper = [1 for i in range(N)]
for i in range(1, N):
	x = N-i-1
	if P[x] < P[x+1]:
		upper[x] = upper[x+1] + 1

skip = [-1,-1]
flg = False
for i in range(N):
	if upper[N-i-1] >= K:
		skip.append(N-i-1)

skip.pop()
deq_min = deque([P[0]])
deq_max = deque([P[0]])
minlen = 1
maxlen = 1
for i in range(1, K):
	while minlen > 0 and deq_min[-1] > P[i]:
		deq_min.pop()
		minlen -= 1
	deq_min.append(P[i])
	minlen += 1
	while maxlen > 0 and deq_max[-1] < P[i]:
		deq_max.pop()
		maxlen -= 1
	deq_max.append(P[i])
	maxlen += 1

ans = 1
next_skip = skip.pop()
for i in range(1, N-K+1):
	new_i = i+K-1
	min_rem = (deq_min[0] == P[i-1])
	max_add = (deq_max[0] < P[new_i])
	if not (min_rem and max_add):
		if i != next_skip:
			ans += 1
	if i == next_skip:
		next_skip = skip.pop()
	if min_rem:
		deq_min.popleft()
		minlen -= 1
	if deq_max[0] == P[i-1]:
		deq_max.popleft()
		maxlen -= 1
	while minlen > 0 and deq_min[-1] > P[new_i]:
		deq_min.pop()
		minlen -= 1
	deq_min.append(P[new_i])
	minlen += 1
	while maxlen > 0 and deq_max[-1] < P[new_i]:
		deq_max.pop()
		maxlen -= 1
	deq_max.append(P[new_i])
	maxlen += 1
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    #新メンバーが最大でないorいなくなったやつが最小でないなら、更新があった
    N,K = MI()
    P = LI()

    max_heap=[]
    min_heap=[]
    includes = set()
    for i in range(K):
        x = P[i]
        heappush(max_heap, -x)
        heappush(min_heap, x)
        includes.add(x)
    

    wrongs=deque()
    for i in range(N-1):
        if P[i]>P[i+1]:
            wrongs.append(i+0.5)
    
    including=deque()
    for w in deepcopy(wrongs):
        if w < K-1:
            including.append(wrongs.popleft())
        else:
            break

    zero_experiense = not including

    ans = 1
    #wrongなしを考慮
    for left in range(1,N-K+1):
        right=left+K-1
        last_mem = P[left-1]

        if including and including[0]<left:
            including.popleft()
        if wrongs and wrongs[0]<right:
            including.append(wrongs.popleft())

        includes.remove(last_mem)
        includes.add(P[right])

        while -max_heap[0] not in includes:
            heappop(max_heap)
        while min_heap[0] not in includes:
            heappop(min_heap)

        if last_mem < min_heap[0] and -max_heap[0] < P[right]:
            pass
        else:
            if not including:
                if zero_experiense:
                    pass
                else:
                    ans += 1
                    zero_experiense = True
            else:
                ans += 1
        heappush(min_heap, P[right])
        heappush(max_heap, -P[right])
    print(ans)

    


if __name__ == '__main__':
    main()

"""#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    #間違ってるところを区間に含む/この含んでいるのが違うなら、あれですよと
    N,K = MI()
    P = LI()
    wrongs=deque()
    including = deque()
    for i in range(N-1):
        if P[i]>P[i+1]:
            wrongs.append(i+0.5)
    including=deque()
    for w in deepcopy(wrongs):
        if w < K-1:
            including.append(wrongs.popleft())
        else:
            break
    ans = 1
    zero_experiense = not including
    #区間の最大より小さいものを新たに含む場合もだめですよと。
    incs = set()
    heap = []
    for i in range(K):
        heappush(heap,-P[i])
        incs.add(P[i])

    for left in range(1,N-K+1):
        incs.remove(P[left-1])
        while -heap[0] not in incs:
            heappop(heap)
        #メンバとheap最大は正しい最大になってる


        update = False
        if including and including[0]<left:
            update = True
            including.popleft()
        if wrongs and wrongs[0]<right:
            update = True
            including.append(wrongs.popleft())


        if update:
            if not including:
                if zero_experiense:
                    incs.add(P[right])
                    heappush(heap,-P[i])
                    continue

                else:
                    zero_experiense=True
            ans += 1
        else:
            maxim = -heap[0]
            if maxim>P[right] and including:
                ans +=1
        incs.add(P[right])
        heappush(heap, -P[right])

    print(ans)
        



if __name__ == '__main__':
    main()"""

Submission status: Accepted

Solution code:
from collections import deque
N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
c = 0
d = 0
q = deque()
p = deque()
for i in range(K):
    if len(q) == 0:
        q.append(i)
    else:
        while len(q) > 0:
            if a[q[len(q)-1]] > a[i]:
                q.pop()
            else:
                q.append(i)
                break
        else:
            q.append(i)

    if len(p) == 0:
        p.append(i)
    else:
        while len(p) > 0:
            if a[p[len(p)-1]] < a[i]:
                p.pop()
            else:
                p.append(i)
                break
        else:
            p.append(i)
    if len(q) == K:
        c += 1

for i in range(K, N):
    if len(q) == 0:
        q.append(i)
    else:
        flag = 0
        while len(q) > 0:
            if a[q[len(q)-1]] > a[i]:
                q.pop()
                flag = 1
            else:
                q.append(i)
                break
        else:
            q.append(i)
        if q[0] == i-K:
            l = q.popleft()
        else:
            flag = 1

    if len(p) == 0:
        p.append(i)
    else:
        while len(p) > 0:
            if a[p[len(p)-1]] < a[i]:
                p.pop()
            else:
                p.append(i)
                break
        else:
            p.append(i)
        if a[p[0]] > a[i]:
            flag = 1

        if p[0] == i-K:
            l = p.popleft()



    if flag == 1:
        ans += 1
    if len(q) == K and flag == 1:
        c += 1

if c > 1:
    ans -= c-1
print(ans)

Submission status: Accepted

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

class BITmax:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, t, x):
    k = t
    s.T[k - 1] = max(s.T[k - 1], x)
    k += k & -k
    while k <= s.N:
      s.T[k - 1] = max(s.T[k - 1], x)
      k += k & -k
  def getV(s, x):
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans = max(ans, s.T[x - 1])
      x -= x & -x
    return ans

class BITmin:
  ini = N
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, t, x):
    k = t
    s.T[k - 1] = min(s.T[k - 1], x)
    k += k & -k
    while k <= s.N:
      s.T[k - 1] = min(s.T[k - 1], x)
      k += k & -k
  def getV(s, x):
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans = min(ans, s.T[x - 1])
      x -= x & -x
    return ans

MA = BITmax(N)
MI = BITmin(N)

La = [0] * N
Li = [0] * N

for i in range(K - 1):
  t = N - i
  MA.update(t, P[t - 1])
  MI.update(t, P[t - 1])
for i in range(K - 2, N):
  t = N - i
  MA.update(t, P[t - 1])
  MI.update(t, P[t - 1])
  La[t - 1] = MA.getV(t + K - 2)
  Li[t - 1] = MI.getV(t + K - 2)

T = [0] * N
cnt = 0
t = 0
for i in range(1, N):
  if P[i] > P[i - 1]:
    cnt += 1
    if cnt >= K - 1:
      T[i - K + 1] = 1
      t += 1
  else:
    cnt = 0

if t != 0:
  t -= 1

for i in range(N - K):
  if T[i] == 1:
    continue
  if Li[i + 1] > P[i] and La[i + 1] < P[i + K]:
    t += 1

print(N - K - t + 1)

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

def solve():
    N, K = map(int, input().split())
    Ps = list(map(int, input().split()))

    ans = N - K + 1

    numAsc = 0
    num = 0
    P0 = -1
    for P in (Ps+[-1]):
        if P0 < P:
            num += 1
        else:
            if num >= K:
                numAsc += num-K+1
            num = 1
        P0 = P
    if numAsc > 0:
        ans -= numAsc - 1

    if K > 2:
        mins = [N] * N
        P = min(Ps[:K+1])
        mins[0] = P
        PQ = [(P, i) for i, P in enumerate(Ps[:K+1])]
        heapify(PQ)
        for i in range(K+1, N):
            heappush(PQ, (Ps[i], i))
            while True:
                P, pos = heappop(PQ)
                if i-K <= pos:
                    mins[i-K] = P
                    heappush(PQ, (P, pos))
                    break

        maxs = [-1] * N
        P = max(Ps[:K+1])
        maxs[0] = P
        PQ = [(-P, i) for i, P in enumerate(Ps[:K+1])]
        heapify(PQ)
        for i in range(K+1, N):
            heappush(PQ, (-Ps[i], i))
            while True:
                P, pos = heappop(PQ)
                if i-K <= pos:
                    maxs[i-K] = -P
                    heappush(PQ, (P, pos))
                    break

        isSorteds = [False] * N
        num = 0
        P0 = -1
        for i, P in enumerate(Ps+[-1]):
            if P0 < P:
                num += 1
                if num >= K-1:
                    isSorteds[i-K+1] = True  ###
            else:
                if num >= K:
                    numAsc += num-K+1
                num = 1
            P0 = P

        for i in range(N-K):
            L, R = Ps[i], Ps[i+K]
            minK, maxK = mins[i], maxs[i]
            if L == minK and R == maxK and not isSorteds[i]:
                ans -= 1

    print(ans)


solve()