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 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())
if N==K:
    print(1)
    exit()
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)

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

Submission status: Wrong Answer

Solution code:
import sys
import random
input = sys.stdin.readline

class Segment_tree():
    def __init__(self, n, arrange):
        self.inf = pow(2, 32)
        self.n = n
        self.arrange = arrange
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
        self.size -= 1
        self.N -= 1
        self.segment = [0]*(self.N) + self.arrange + [0]*(self.size-self.N-self.n)
        #この次の処理は、求められる動作に応じて変化させる。ここでは区間最小値問題のコードを書く。
        for i in range(self.N-1, -1, -1):
            self.segment[i] = min([self.segment[2*i+1], self.segment[2*i+2]])
        
    def undate(self, i, x):
        i += (self.N-1)
        self.segment[i] = x
        while i > 0:
            i = (i-1)//2
            self.segment[i] = min([self.segment[2*i+1], self.segment[2*i+2]])
        
    def find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.inf
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            return min([find_l, find_r])
    
    def count(self, l, r):
        return self.find(l, r, 0, 0, self.size-self.N)

class Segment_tree2():
    def __init__(self, n, arrange):
        self.inf = pow(2, 32)
        self.n = n
        self.arrange = arrange
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
        self.size -= 1
        self.N -= 1
        self.segment = [0]*(self.N) + self.arrange + [0]*(self.size-self.N-self.n)
        #この次の処理は、求められる動作に応じて変化させる。ここでは区間最小値問題のコードを書く。
        for i in range(self.N-1, -1, -1):
            self.segment[i] = max([self.segment[2*i+1], self.segment[2*i+2]])
        
    def undate(self, i, x):
        i += (self.N-1)
        self.segment[i] = x
        while i > 0:
            i = (i-1)//2
            self.segment[i] = max([self.segment[2*i+1], self.segment[2*i+2]])
        
    def find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            return max([find_l, find_r])
    
    def count(self, l, r):
        return self.find(l, r, 0, 0, self.size-self.N)



def solve(n, k, p):
    segment_min = Segment_tree(n, p)
    segment_max = Segment_tree2(n, p)
    
    res = n-k+1
    for i in range(n-k):
        x, y = p[i], p[k+i]
        a = segment_min.count(i+1, k+i-1)
        b = segment_max.count(i+1, k+i-1)
        if x < a and b < y:
            res -= 1
    
    return res

def solve2(n, a):
    res = 1
    for i in range(n-2):
        if (a[i] > a[i+1]) or (a[i+1] > a[i+2]):
            res += 1
    return res
    
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    
    if k == 2:
        ans = solve2(n, p)
    else:
        ans = solve(n, k, p)
    print(ans)
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    from collections import deque
    N, K = map(int, readline().split())
    P = list(map(int, readline().split()))

    if N == K:
        return print(1)

    p_min = [0] * (N - K)
    p_max = [0] * (N - K)
    p_asc = [0] * (N - K + 1)

    def calc_min():
        que = deque()
        que.append(P[0])

        for i in range(1, K + 1):
            cur = P[i]
            while que and cur < que[-1]:
                que.pop()
            que.append(cur)
        p_min[0] = que[0]

        for i in range(N - K - 1):
            prev = P[i]
            cur = P[i + K + 1]
            if que[0] == prev:
                que.popleft()
            while que and cur < que[-1]:
                que.pop()
            que.append(cur)
            p_min[i + 1] = que[0]

    def calc_max():
        que = deque()
        que.append(P[0])

        for i in range(1, K + 1):
            cur = P[i]
            while que and cur > que[-1]:
                que.pop()
            que.append(cur)
        p_max[0] = que[0]

        for i in range(N - K - 1):
            prev = P[i]
            cur = P[i + K + 1]
            if que[0] == prev:
                que.popleft()
            while que and cur > que[-1]:
                que.pop()
            que.append(cur)
            p_max[i + 1] = que[0]

    def calc_asc():
        prev = -1
        cnt = 0
        for i in range(K):
            cur = P[i]
            if prev < cur:
                cnt += 1
            prev = cur
        p_asc[0] = cnt

        for i in range(N - K):
            cur = P[i + K]
            if prev < cur:
                p_asc[i + 1] = min(p_asc[i] + 1, K)
            else:
                p_asc[i + 1] = 1
            prev = cur

    calc_min()
    calc_max()
    calc_asc()

    uf = UnionFind(N - K + 1)

    asc_list = []
    for i in range(N - K + 1):
        if p_asc[i] == K:
            asc_list.append(i)
    if len(asc_list) > 1:
        for i in range(1, len(asc_list)):
            uf.union(asc_list[0], asc_list[i])

    for i in range(N - K):
        if p_min[i] == P[i] and p_max[i] == P[i + K]:
            uf.union(i, i + 1)

    print(uf.group_count())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    from collections import deque
    N, K = map(int, readline().split())
    P = list(map(int, readline().split()))

    p_min = [0] * (N - K + 1)
    p_max = [0] * (N - K + 1)
    p_asc = [0] * (N - K + 1)

    def calc_min():
        que = deque()
        que.append(P[0])

        for i in range(1, K):
            cur = P[i]
            while que and cur < que[-1]:
                que.pop()
            que.append(cur)
        p_min[0] = que[0]

        for i in range(N - K):
            prev = P[i]
            cur = P[i + K]
            if que[0] == prev:
                que.popleft()
            while que and cur < que[-1]:
                que.pop()
            que.append(cur)
            p_min[i + 1] = que[0]

    def calc_max():
        que = deque()
        que.append(P[0])

        for i in range(1, K):
            cur = P[i]
            while que and cur > que[-1]:
                que.pop()
            que.append(cur)
        p_max[0] = que[0]

        for i in range(N - K):
            prev = P[i]
            cur = P[i + K]
            if que[0] == prev:
                que.popleft()
            while que and cur > que[-1]:
                que.pop()
            que.append(cur)
            p_max[i + 1] = que[0]

    def calc_asc():
        prev = -1
        cnt = 0
        for i in range(K):
            cur = P[i]
            if prev < cur:
                cnt += 1
            prev = cur
        p_asc[0] = cnt

        for i in range(N - K):
            cur = P[i + K]
            if prev < cur:
                p_asc[i + 1] = min(p_asc[i] + 1, K)
            else:
                p_asc[i + 1] = 1
            prev = cur

    calc_min()
    calc_max()
    calc_asc()

    uf = UnionFind(N - K + 1)

    asc_list = []
    for i in range(N - K + 1):
        if p_asc[i] == K:
            asc_list.append(i)
    if len(asc_list) > 1:
        for i in range(1, len(asc_list)):
            uf.union(asc_list[0], asc_list[i])

    for i in range(N - K):
        if p_min[i] == P[i] and p_max[i + 1] == P[i + K]:
            uf.union(i, i + 1)

    print(uf.group_count())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

def slide_min(A, K):
    deq, ret = deque([]), []
    for k in range(len(A)):
        while deq and A[deq[-1]] >= A[k]:
            deq.pop()
        deq.append(k)
 
        if k < K - 1:
            continue
 
        if deq[0] + K <= k:
            deq.popleft()
        ret.append(A[deq[0]])
 
    return ret

MIN = slide_min(P, K)
MAX = list(map(lambda x: -x, slide_min(list(map(lambda x: -x, P)), K)))

ans = 0

for i in range(N-K):
    if MIN[i] == P[i] and MAX[i+1] == P[i+K]:
        ans += 1

tmp = 1
cnt = 0

for i in range(N-1):
    if P[i] < P[i+1]:
        tmp += 1
    else:
        tmp = 1
    if tmp >= K:
        cnt += 1

ans += max(0, cnt - 1)

ans = N - K + 1 - ans

print(ans)

Submission status: Wrong Answer

Solution code:
class SegTree:  # 0-index !!!
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  # O(log(n))
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):  # l = r の場合はたぶんバグるので注意
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

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

# ---------------------- #

n, k = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

min_seg = SegTree(P, fx=min, ex=10**18)
max_seg = SegTree(P, fx=max, ex=0)

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

ans = 0
no_count = 0
min_out_flag = False
for i in range(n - k + 1):
    if asc_count[i + k - 1] >= k:
        no_count += 1
    if not min_out_flag or P[i + k - 1] != max_seg.query(i, i + k):
        ans += 1
    if P[i] == min_seg.query(i, i + k):
        min_out_flag = True
    else:
        min_out_flag = False

print(ans - max(no_count - 1, 0))

Submission status: Wrong Answer

Solution code:
class SegTree:  # 0-index !!!
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  # O(log(n))
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):  # l = r の場合はたぶんバグるので注意
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

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

# ---------------------- #

def flag_func(a, b):
    return a and b

n, k = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

min_seg = SegTree(P, fx=min, ex=10**18)
max_seg = SegTree(P, fx=max, ex=0)

count = 1
flags = [False] * n
for i in range(1, n):
    if P[i] > P[i - 1]:
        count += 1
    else:
        count = 1
    if count >= k:
        flags[i - k + 1] = True

ans = 0
no_count = 0
min_out_flag = False
for i in range(n - k + 1):
    if flags[i]:
        no_count += 1
    if not min_out_flag or P[i + k - 1] != max_seg.query(i, i + k):
        ans += 1
    if P[i] == min_seg.query(i, i + k):
        min_out_flag = True
    else:
        min_out_flag = False

print(ans - max(no_count - 1, 0))

Submission status: Wrong Answer

Solution code:
class SegTree:  # 0-index !!!
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  # O(log(n))
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):  # l = r の場合はたぶんバグるので注意
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

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

# ---------------------- #

def flag_func(a, b):
    return a and b

n, k = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

min_seg = SegTree(P, fx=min, ex=10**18)
max_seg = SegTree(P, fx=max, ex=0)

count = 1
tmp = P[0]
for i in range(1, k):
    if P[i] > tmp:
        count += 1
    else:
        count = 1

ans = 0
min_out_flag = False
for i in range(n - k + 1):
    if P[i + k - 1] == max_seg.query(i, i + k):
        count += 1
        if not min_out_flag and count < k:
            ans += 1
    else:
        count = 1
        ans += 1
    if P[i] == min_seg.query(i, i + k):
        min_out_flag = True
    else:
        min_out_flag = False

print(ans)

Submission status: Wrong Answer

Solution code:
class SegTree:  # 0-index !!!
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  # O(log(n))
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):  # l = r の場合はたぶんバグるので注意
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

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

# ---------------------- #

n, k = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

min_seg = SegTree(P, fx=min, ex=10**18)
max_seg = SegTree(P, fx=max, ex=0)

count = 1
ascending_count = [1] * n
for i in range(1, n):
    if P[i - 1] < P[i]:
        ascending_count[i] = ascending_count[i - 1] + 1

no_count = 0
if ascending_count[k - 1] >= k:
    no_count += 1

ans = 1
for i in range(1, n - k + 1):
    if ascending_count[i + k - 1] >= k:
        no_count += 1
    if P[i - 1] != min_seg.query(i - 1, i + k) or P[i + k - 1] != max_seg.query(i - 1, i + k):
        ans += 1

print(ans - max(no_count - 1, 0))

Submission status: Wrong Answer

Solution code:
def fall(A,N):
  ans = [False]*N
  m = -float('inf')
  for i in range(N):
    if A[i]<m:
      ans[i] = True
    else:
      m = A[i]
  return ans

def solve():
  N, K = map(int, input().split())
  P = list(map(int, input().split()))
  before = fall(P,N)
  after = fall([-i for i in P[::-1]],N)[::-1]
  ans = 1
  for i in range(N):
    j = i+K
    if j>=N-1:
      break
    if before[i] or after[i] or before[j] or after[j]:
      ans += 1
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
def fall(A,N):
  ans = [False]*N
  m = -float('inf')
  for i in range(N):
    if A[i]<m:
      ans[i] = True
    else:
      m = A[i]
  return ans

def solve():
  N, K = map(int, input().split())
  P = list(map(int, input().split()))
  before = fall(P,N)
  after = fall([-i for i in P[::-1]],N)[::-1]
  ans = 1
  for i in range(N):
    j = i+K
    if j==N:
      break
    if after[i] or before[j]:
      ans += 1
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
def fall(A,N):
  ans = [False]*N
  m = -float('inf')
  for i in range(N):
    if A[i]<m:
      ans[i] = True
    else:
      m = A[i]
  return ans

def solve():
  N, K = map(int, input().split())
  P = list(map(int, input().split()))
  before = fall(P,N)
  after = fall([-i for i in P[::-1]],N)[::-1]
  ans = 1
  for i in range(1,N):
    j = i+K-2
    if j==N-1:
      break
    if after[j] or before[i]:
      ans += 1
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
from bisect import *
def fall(A,N):
  ans = [False]*N
  lis = []
  for i in range(N):
    if bisect_right(lis,A[i])<i:
      ans[i] = True
    insort_right(lis,A[i])
  return ans

def solve():
  N, K = map(int, input().split())
  P = list(map(int, input().split()))
  before = fall(P,N)
  after = fall([-i for i in P[::-1]],N)[::-1]
  ans = 1
  for i in range(1,N):
    j = i+K-2
    if j==N-1:
      break
    if after[j] or before[i]:
      ans += 1
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
class SegTree:  # 0-index !!!
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  # O(log(n))
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):  # l = r の場合はたぶんバグるので注意
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

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

# ---------------------- #

def flag_func(a, b):
    return a and b

n, k = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

min_seg = SegTree(P, fx=min, ex=10**18)
max_seg = SegTree(P, fx=max, ex=0)

count = 1
tmp = P[0]
for i in range(1, k):
    if P[i] > tmp:
        count += 1
    else:
        count = 1

ans = 0
min_out_flag = False
for i in range(n - k + 1):
    if P[i + k - 1] == max_seg.query(i, i + k):
        count += 1
        if not min_out_flag and count != k:
            ans += 1
    else:
        count = 1
        ans += 1
    if P[i] == min_seg.query(i, i + k):
        min_out_flag = True
    else:
        min_out_flag = False

print(ans)

Submission status: Wrong Answer

Solution code:
class SegTree:  # 0-index !!!
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  # O(log(n))
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):  # l = r の場合はたぶんバグるので注意
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

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

# ---------------------- #

def flag_func(a, b):
    return a and b

n, k = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

min_seg = SegTree(P, fx=min, ex=10**18)
max_seg = SegTree(P, fx=max, ex=0)

ans = 1
min_out_flag = True
for i in range(n - k):
    if not (min_out_flag and P[i + k - 1] == max_seg.query(i, i + k)):
        ans += 1
    if P[i] == min_seg.query(i, i + k):
        min_out_flag = True
    else:
        min_out_flag = False

print(ans)