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: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,K = LI()
    P = LI()

    class Node:
        def __init__(self, x):
            self.data = x
            self.count = 1
            self.left = None
            self.right = None

    def insert(node, x):
        if node is None: return Node(x)
        if node.data == x:
            node.count += 1
        elif x < node.data:
            node.left = insert(node.left, x)
        else:
            node.right = insert(node.right, x)
        return node

    def search_min(node):
        if node.left is None: return node.data
        return search_min(node.left)

    def search_max(node):
        if node.right is None: return node.data
        return search_max(node.right)

    def delete_min(node):
        if node.left is None:
            if node.count > 1:
                node.count -= 1
            else:
                return node.right
        else:
            node.left = delete_min(node.left)
        return node

    def delete(node, x):
        if node:
            if x == node.data:
                if node.count > 1:
                    node.count -= 1
                elif node.left is None:
                    return node.right
                elif node.right is None:
                    return node.left
                else:
                    node.data = search_min(node.right)
                    node.right = delete_min(node.right)
            elif x < node.data:
                node.left = delete(node.left, x)
            else:
                node.right = delete(node.right, x)
        return node

    root = None
    cnt = 0
    bp = -1
    for i in range(K):
        root = insert(root,P[i])
        if P[i] > bp:
            cnt += 1
        else:
            cnt = 0
        bp = P[i]

    if cnt >= K:
        flg = 1
        ans = 0
    else:
        flg = 0
        ans = 1
    for i in range(1,N-K):
        if P[i+K-1] > bp:
            cnt += 1
        else:
            cnt = 0
        bp = P[i+K-1]
        if search_min(root) == P[i-1] and search_max(root) < P[i+K-1] or cnt >= K:
            flg = 1
        else:
            ans +=1
        root = insert(root,P[i+K-1])
        root = delete(root,P[i-1])

    print(ans+flg)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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)
    prev_min = seg_min.query(0, k)
    prev_max = seg_max.query(0, k)
    res = 1
    for i in range(1, n - k + 1):
        if P[i - 1] != prev_min or P[i + k] < prev_max:
            res += 1
        prev_min = seg_min.query(i, i + k)
        prev_max = seg_max.query(i, i + k)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
N,K=map(int, input().split())
P=list(map(int, input().split()))
D=[0]*(N-1)
for i in range(N-1):
  if P[i]>P[i+1]:
    D[i]=1
E=[]
D.append(1)
cnt=0
for i in range(len(D)):
  if D[i]==0:
    cnt+=1
  elif cnt>0:
    E.append(cnt)
    cnt=0
ans=N+1-K
for i in E:
  if i>=K:
    ans-=i-K+1
if max(E)<K-1:
  ans-=1
print(ans)

Submission status: Runtime Error

Solution code:
import math
import numpy as np
import decimal
import collections
import itertools
import sys
#Union-Find
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    p = find(x)
    q = find(y)
    if p == q:
        return None
    if p > q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
n = 0
par = [-1 for i in range(n)]

#素数関連
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True
#nCr
mod = 10 ** 9 + 7
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (n + 1)
fi = [1] * (n + 1)
for i in range(1, n + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
#BIT
BIT = [0] * (n + 1)
def add(i, x):
    while i <= n:
        BIT[i] += x
        i += i & -i
def query(i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
cnt = 0
li = [1 for i in range(n - k + 1)]
for i in range(1, k):
    if p[i - 1] > p[i]:
        cnt += 1
if cnt == 0:
    li[0] = 0
for i in range(k, n):
    if p[i - 1] > p[i]:
        cnt += 1
    if p[i - k] > p[i - k + 1]:
        cnt -= 1
    if cnt == 0:
        li[i - k + 1] = 0
Q1 = deque([0 for i in range(n - k)])
Q2 = deque([0 for i in range(n - k)])
L1, L2 = list(Q1), list(Q2)
for i in range(n):
    while Q1 and p[Q1[-1]] > p[i]:
        Q1.pop()
    while Q2 and p[Q2[-1]] < p[i]:
        Q2.pop()
    Q1.append(i)
    Q2.append(i)
    if Q1[0] == i - k - 1:
        Q1.popleft()
    if Q2[0] == i - k - 1:
        Q2.popleft()
    if i >= k - 2:
        L1[i - k] = p[Q1[0]]
        L2[i - k] = p[Q2[0]]
ans = 0
for i in range(1, n - k - 1):
    if p[i - 1] > L1[i] or p[i + k - 1] < L2[i]:
        if li[i + 1] > 0:
            ans += 1
print(ans - min(li) + li[0] + 1)

Submission status: Runtime Error

Solution code:
import math
import numpy as np
import decimal
import collections
import itertools
import sys
#Union-Find
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    p = find(x)
    q = find(y)
    if p == q:
        return None
    if p > q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
n = 0
par = [-1 for i in range(n)]

#素数関連
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True
#nCr
mod = 10 ** 9 + 7
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (n + 1)
fi = [1] * (n + 1)
for i in range(1, n + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
#BIT
BIT = [0] * (n + 1)
def add(i, x):
    while i <= n:
        BIT[i] += x
        i += i & -i
def query(i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
cnt = 0
li = [1 for i in range(n - k + 1)]
for i in range(1, k):
    if p[i - 1] > p[i]:
        cnt += 1
if cnt == 0:
    li[0] = 0
for i in range(k, n):
    if p[i - 1] > p[i]:
        cnt += 1
    if p[i - k] > p[i - k + 1]:
        cnt -= 1
    if cnt == 0:
        li[i - k + 1] = 0
Q1 = deque([0 for i in range(n - k + 1)])
Q2 = deque([0 for i in range(n - k + 1)])
L1, L2 = list(Q1), list(Q2)
for i in range(n):
    while Q1 and p[Q1[-1]] > p[i]:
        Q1.pop()
    while Q2 and p[Q1[-1]] < p[i]:
        Q2.pop()
    Q1.append(i)
    Q2.append(i)
    if Q1[0] == i - k:
        Q1.popleft()
    if Q2[0] == i - k:
        Q2.popleft()
    if i + 1 >= k:
        L1[i - k + 1] = p[Q1[0]]
        L2[i - k + 1] = p[Q2[0]]
ans = 0
for i in range(1, n - k):
    if p[i - 1] > L1[i] or p[i + k] < L2[i]:
        if li[i + 1] > 0:
            ans += 1
print(ans - min(li) + li[0] + 1)

Submission status: Runtime Error

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)
    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: Runtime Error

Solution code:
T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

d1 = T1*(A1-B1)
d2 = T2*(A2-B2)
if d1>d2:
    d1 *= -1
    d2 *= -1

if (d1>0 and d1+d2>0) or (d1<0 and d1+d2<0):
    print(0)
elif d1+d2==0:
    print("infinity")
else:
    v = (abs(d1)//(d1+d2))
    ans = v*2
    pos = d1+v*(d1+d2)
    if pos<0 and pos+d2>=0:
        ans += 1
    print(pos)

Submission status: Runtime Error

Solution code:
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = 0
l = [1] * (n - k + 1)
for i in range(k - 1):
    if p[i] > p[i + 1]:
        c += 1
if c == 0:
    l[0] = 0
for i in range(k - 1, n - 1):
    if p[i] > p[i + 1]:
        c += 1
    if p[i - k + 1] > p[i - k + 2]:
        c -= 1
    if c == 0:
        l[i - k + 2] = 0
k -= 1
qa = deque([])
a = [0] * (n - k + 1)
qb = deque([])
b = [0] * (n - k + 1)
for i in range(n):
    while qa and p[qa[-1]] > p[i]:
        qa.pop()
    while qb and p[qb[-1]] < p[i]:
        qb.pop()
    qa.append(i)
    qb.append(i)
    if qa[0] == i - k:
        qa.popleft()
    if qb[0] == i - k:
        qb.popleft()
    a[i - k + 1] = p[qa[0]]
    b[i - k + 1] = p[qb[0]]
ans = 1
for i in range(n - k - 1):
    if p[i] > a[i + 1] or b[i + 1] > p[i + k + 1] and l[i]:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
t = 0
res = 0
c = 0
for i in range(k - 1):
    if p[i] > p[i + 1]:
        c += 1
if c == 0:
    t = 1
    res += 1
for i in range(k - 1, n - 1):
    if p[i] > p[i + 1]:
        c += 1
    if p[i - k + 1] > p[i - k + 2]:
        c -= 1
    if c == 0:
        t = 1
        res += 1
k -= 1
qa = deque([])
a = [0] * (n - k + 1)
qb = deque([])
b = [0] * (n - k + 1)
for i in range(n):
    while qa and p[qa[-1]] > p[i]:
        qa.pop()
    while qb and p[qb[-1]] < p[i]:
        qb.pop()
    qa.append(i)
    qb.append(i)
    if qa[0] == i - k:
        qa.popleft()
    if qb[0] == i - k:
        qb.popleft()
    a[i - k + 1] = p[qa[0]]
    b[i - k + 1] = p[qb[0]]
exit(0)
ans = 1
for i in range(n - k - 1):
    if p[i] > a[i + 1] or b[i + 1] > p[i + k + 1]:
        ans += 1
print(ans + t - res)

Submission status: Runtime Error

Solution code:
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
t = 0
res = 0
c = 0
for i in range(k - 1):
    if p[i] > p[i + 1]:
        c += 1
if c == 0:
    t = 1
    res += 1
for i in range(k - 1, n - 1):
    if p[i] > p[i + 1]:
        c += 1
    if p[i - k + 1] > p[i - k + 2]:
        c -= 1
    if c == 0:
        t = 1
        res += 1
k -= 1
qa = deque([])
a = [0] * (n - k + 1)
qb = deque([])
b = [0] * (n - k + 1)
for i in range(n):
    while qa and p[qa[-1]] > p[i]:
        qa.pop()
    while qb and p[qb[-1]] < p[i]:
        qb.pop()
    qa.append(i)
    qb.append(i)
    if qa[0] == i - k:
        qa.popleft()
    if qb[0] == i - k:
        qb.popleft()
    a[i - k + 1] = p[qa[0]]
    b[i - k + 1] = p[qb[0]]
ans = 1
for i in range(n - k - 1):
    if p[i] > a[i + 1] or b[i + 1] > p[i + k + 1]:
        ans += 1
print(ans + t - res)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
N, K , *P = map(int, open('0').read().split())
mhq = []
Mhq = []
for c in P[:K]:
  heappush(mhq,c)
  heappush(Mhq,-c)

ans = 1
log = set()
for i,c in enumerate(P[K:]):
  while mhq[0] in log:
    heappop(mhq)
  while -Mhq[0] in log:
    heappop(Mhq)
  d = P[i]
  m = mhq[0]
  M = -Mhq[0]
  log.add(d)
  heappush(mhq,c)
  heappush(Mhq,-c)
  if not (m==d and M<c):
    ans += 1
p = P[0]
m = 1
x = 0
for c in P[1:]:
  if p<c:
    m += 1
  else:
    if m>=K:
      x += 1
    m = 1
  p = c
if m>=K:
  x += 1
if x!=0:
  ans -= x-1
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
N, K , *P = map(int, open('0').read().split())
mhq = []
Mhq = []
for c in P[:K]:
  heappush(mhq,c)
  heappush(Mhq,-c)

ans = 1
log = set()
for i,c in enumerate(P[K:]):
  while mhq[0] in log:
    heappop(mhq)
  while -Mhq[0] in log:
    heappop(Mhq)
  d = P[i]
  m = mhq[0]
  M = -Mhq[0]
  log.add(d)
  heappush(mhq,c)
  heappush(Mhq,-c)
  if not (m==d and M<c):
    ans += 1
p = P[0]
m = 1
x = 0
for c in P[1:]:
  if p<c:
    m += 1
  else:
    if m>=K:
      x += 1
    m = 1
  p = c
if m>=K:
  x += 1
print(ans-x+1)

Submission status: Runtime Error

Solution code:
import ipdb
from collections import deque
from bisect import bisect_right
N,K = map(int,input().split())
P = list(map(int,input().split()))
Lmax = []
Lmin = []
if P[1]>P[0]:
    flag = 1
else:
    flag = -1
for i in range(2,N):
    if P[i]>P[i-1]:
        if flag==1:continue
        else:
            Lmin.append([i-1,P[i-1]])
            flag = 1
    else:
        if flag==1:
            Lmax.append([i-1,P[i-1]])
            flag = -1
        else:continue
cnt = 0
flagMono = 0
indmin = bisect_right(Lmin,[K-1,P[K-1]])
Smax = deque([0])
Smin = deque([0])
for i in range(1,K):
    while Smax:
        if P[Smax[-1]]<P[i]:
            Smax.pop()
        else:break
    Smax.append(i)
    while Smin:
        if P[Smin[-1]]>P[i]:
            Smin.pop()
        else:break
    Smin.append(i)    
if P[0]==P[Smin[0]] and P[K-1]==P[Smax[0]] and (len(Lmin)==0 or indmin==0 or Lmin[indmin-1][0]==0):
    flagMono=1
    cnt += 1
elif P[0]==P[Smin[0]] and K<N and P[K]>P[Smax[0]]:
    pass
else:
    cnt += 1
for i in range(1,N-K+1):
    if Smax[0]==i-1:
        Smax.popleft()
    while Smax:
        if P[Smax[-1]]<P[i+K-1]:
            Smax.pop()
        else:break
    Smax.append(i+K-1)
    if Smin[0]==i-1:
        Smin.popleft()
    while Smin:
        if P[Smin[-1]]>P[i+K-1]:
            Smin.pop()
        else:break
    Smin.append(i+K-1)
    indmin = bisect_right(Lmin,[i+K-1,P[i+K-1]])
    if P[i]==P[Smin[0]] and P[i+K-1]==P[Smax[0]] and (len(Lmin)==0 or indmin==0 or Lmin[indmin-1][0]<=i):
        if flagMono==0:
            flagMono = 1
            cnt += 1
        else:
            pass
    elif P[i]==P[Smin[0]] and i+K<N and P[i+K]>P[Smax[0]]:
        continue
    else:
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
Q = P[:K]
R = sorted(Q)
f = 0
if R == Q:
    f == 1
if N == K:
    ans = 1
else:
    ans = 1
    m = R[0]
    for i in range(K,N):
        x = Q.pop(0)
        y = P[i]
        Q.append(y)
        R = Q.sorted()
        if R[-1] == y:
            if m == x:
                continue
            else:
                if f == 0:
                    ans += 1
        else:
            ans += 1
        if R == Q:
            f = 1
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
Q = P[:K]
R = sorted(Q)
if R == Q:
    f == 1
if N == K:
    ans = 1
else:
    ans = 1
    m = R[0]
    for i in range(K,N):
        x = Q.pop(0)
        y = P[i]
        Q.append(y)
        R = Q.sorted()
        if R[-1] == y:
            if m == x:
                continue
            else:
                if f == 0:
                    ans += 1
        else:
            ans += 1
        if R == Q:
            f = 1
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input())
P = list(map(int,input().split()))
Q = P[:K]
R = sorted(Q)
if R == Q:
    f == 1
if N == K:
    ans = 1
else:
    ans = 1
    m = R[0]
    for i in range(K,N):
        x = Q.pop(0)
        y = P[i]
        Q.append(y)
        R = Q.sorted()
        if R[-1] == y:
            if m == x:
                continue
            else:
                if f == 0:
                    ans += 1
        else:
            ans += 1
        if R == Q:
            f = 1
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input())
P = 
Q = P[:K]
R = sorted(Q)
if R == Q:
    f == 1
if N == K:
    ans = 1
else:
    ans = 1
    m = R[0]
    for i in range(K,N):
        x = Q.pop(0)
        y = P[i]
        Q.append(y)
        R = Q.sorted()
        if R[-1] == y:
            if m == x:
                continue
            else:
                if f == 0:
                    ans += 1
        else:
            ans += 1
        if R == Q:
            f = 1
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import copy

#import sys
#input = sys.stdin.readline

n,k = map(int,input().split())
p = [int(i) for i in input().split()]

p_list = copy.deepcopy(p)

ini_list = p_list.sort()
ini_min = p_list[0]
ini_max = p_list[k-1]

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

ans = 1

cnt_min = ini_min
cnt_max = ini_max
cnt_list = p_list[:k]

for i in range(n-k):
    #print(i,ans)
    if cnt_min != p[i] or cnt_max > p[k+i]:
        ans += 1
    
    idx = bisect.bisect_left(cnt_list,p[i])
    del cnt_list[idx]
    
    idx = bisect.bisect_left(cnt_list,p[k+i])
    cnt_list.insert(idx,p[k+i])
    
    cnt_min = cnt_list[0]
    cnt_max = cnt_list[k-1]

print(ans)

Submission status: Runtime Error

Solution code:
import bisect

#import sys
#input = sys.stdin.readline

n,k = map(int,input().split())
p = [int(i) for i in input().split()]

ini_list = p.sort()
ini_min = ini_list[0]
ini_max = ini_list[k-1]

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

ans = 1

cnt_min = ini_min
cnt_max = ini_max
cnt_list = ini_list

for i in range(n-k):
    #print(i,ans)
    if cnt_min != p[i] or cnt_max > p[k+i]:
        ans += 1
    
    idx = bisect.bisect_left(cnt_list,p[i])
    del cnt_list[idx]
    
    idx = bisect.bisect_left(cnt_list,p[k+i])
    cnt_list.insert(idx,p[k+i])
    
    cnt_min = cnt_list[0]
    cnt_max = cnt_list[k-1]

print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import heapq

#import sys
#input = sys.stdin.readline

n,k = map(int,input().split())
p = [int(i) for i in input().split()]

ini_list = sorted(p[:k])
ini_min = ini_list[0]
ini_max = ini_list[k-1]

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

ans = 1

cnt_min = ini_min
cnt_max = ini_max
cnt_list = ini_list

for i in range(n-k):
    #print(i,ans)
    if cnt_min != p[i] or cnt_max > p[k+i]:
        ans += 1
    
    idx = bisect.bisect_left(cnt_list,p[i])
    del cnt_list[idx]
    
    heapq.heappush(cnt_list,p[k+i])
    #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: Runtime Error

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


def dfs(digd, tmpk):
    if tmpk == k:
        ans = {}
        for i in range(n):
            tmp = 0
            for dig in v[i]:
                if tmp + digd[int(dig)] > len(w[i]):
                    return False, {}
                elif int(dig) not in ans:
                    ans[int(dig)] = w[i][tmp : tmp + digd[int(dig)]]
                    tmp += digd[int(dig)]
                else:
                    if ans[int(dig)] != w[i][tmp : tmp + digd[int(dig)]]:
                        return False, {}
                    else:
                        tmp += digd[int(dig)]
            if tmp != len(w[i]):
                return False, {}
        return True, ans
    else:
        for i in range(1, 4):
            digd[tmpk + 1] = i
            is_finished, ans = dfs(digd, tmpk + 1)
            if is_finished:
                return True, ans
        return False, {}


k, n = map(int, input().split())
v, w = [], []
for _ in range(n):
    _v, _w = input().strip().split()
    v.append(_v)
    w.append(_w)
digd = {}
_, ans = dfs(digd, 0)
for i in range(1, k + 1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
n, k = map(int, input().split())
p = deque(map(int, input().split()))
q = deque()
dp = np.zeros(n+1)
dp[k:] += 1
for i in range(k):
    x = p.popleft()
    q.append(x)
print(p)
print(q)
print(dp)
q.popleft()

for i in range(k, n):
    x = p.popleft()
    if max(q) > x:
        dp[i+1:] += 1
        q.popleft()
    else:
        y = q.popleft()
        if min(q) < y:
            dp[i+1:] += 1
    q.append(x)
    print(p)
    print(q)
    print(dp)
print(dp)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

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

count = 1
for i in range(n-k+1):
    if not isInc(p[i:i+k]):
        count+=1
    
def isInc(numList):
    for i in range(len(numList)-1):
        if numList[i]>numList[i+1]:
            return False
    return True

print(count)

Submission status: Runtime Error

Solution code:
import bisect

#import sys
#input = sys.stdin.readline

n,k = map(int,input().split())
p = [int(i) for i in input().split()]

ini_list = sorted(p[:k])
ini_min = min(p[:k])
ini_max = max(p[:k])

ans = 1

cnt_min = ini_min
cnt_max = ini_max
cnt_list = ini_list

for i in range(n-k):
    #print(i,ans)
    if cnt_min == p[i] and cnt_max <= p[k+i]:
        continue
    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: Runtime Error

Solution code:
import bisect
import heapq

import sys
#input = sys.stdin.readline

n,k = map(int,input().split())
p = [int(i) for i in input().split()]

ini_list = sorted(p[:k])
ini_min = min(p[:k])
ini_max = max(p[:k])

ans = 1

cnt_min = ini_min
cnt_max = ini_max
cnt_list = ini_list

for i in range(n-k):
    #print(i,ans)
    if cnt_min == p[i] and cnt_max <= p[k+i]:
        continue
    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: Runtime Error

Solution code:
import bisect
import heapq

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
p = [int(i) for i in input().split()]

ini_list = sorted(p[:k])
ini_min = min(p[:k])
ini_max = max(p[:k])

ans = 1

cnt_min = ini_min
cnt_max = ini_max
cnt_list = ini_list

for i in range(n-k):
    #print(i,ans)
    if cnt_min == p[i] and cnt_max <= p[k+i]:
        continue
    else:
        ans += 1
    
    idx = bisect.bisect_left(cnt_list,p[i])
    del cnt_list[idx]
    
    idx = bisect.bisect_left(cnt_list,p[k+i])
    bisect.insort(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)