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 UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        """
        x: child
        ret-> node
        xのグループの代表を見つける
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        union (x ,y)
        x,y: node
        ret->None
        """
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

    def same(self, x, y):
        """
        return true if x and y are in same group
        """
        return self.find(x) == self.find(y)

    def connectedNum(self, x):
        """
        return size of the group x belong to
        """
        return self.size[self.find(x)]

    def is_connected(self):
        """
        return true is all node is in one group
        """
        return self.connectedNum(0) == len(self.parent)

    def componentNum(self):
        """
        return componentNum
        """
        par_set=set()
        for p in self.parent:
            par_set.add(self.find(p))
        return len(par_set)

class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


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


Seg_min = SegmentTree(N,min)
Seg_max = SegmentTree(N,max,0)
for i,p in enumerate(P):
    Seg_min.set(i,p)
    Seg_max.set(i,p)
Seg_min.build()
Seg_max.build()

inc=[0]*(N+1)
for i in range(N-1):
    if P[i+1]>P[i]:
        inc[i+1]=1

for i in range(N):
    if inc[i+1]!=0:
        inc[i+1]+=inc[i]

Un=UnionFind(N-K+1)
sorted_seg_par=None

for i in range(N-K+1):
    #start=iとする
    if inc[i+K-1]>=K-1:#[i,i+K]はsorted
        if sorted_seg_par is None:
            sorted_seg_par=i
        else:
            Un.union(sorted_seg_par,i)
    elif i+1<N-K and P[i]==Seg_min.query(i,i+K+1) and P[i+K]==Seg_max.query(i,i+K+1):#[i,i+K]と[i+1,i+K+1]はequivalent
        Un.union(i,i+1)
print(Un.componentNum())

Submission status: Wrong Answer

Solution code:
class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        """
        x: child
        ret-> node
        xのグループの代表を見つける
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        union (x ,y)
        x,y: node
        ret->None
        """
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

    def same(self, x, y):
        """
        return true if x and y are in same group
        """
        return self.find(x) == self.find(y)

    def connectedNum(self, x):
        """
        return size of the group x belong to
        """
        return self.size[self.find(x)]

    def is_connected(self):
        """
        return true is all node is in one group
        """
        return self.connectedNum(0) == len(self.parent)

    def componentNum(self):
        """
        return componentNum
        """
        par_set=set()
        for p in self.parent:
            par_set.add(self.find(p))
        return len(par_set)

class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


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


Seg_min = SegmentTree(N,min)
Seg_max = SegmentTree(N,max,0)
for i,p in enumerate(P):
    Seg_min.set(i,p)
    Seg_max.set(i,p)
Seg_min.build()
Seg_max.build()

inc=[0]*(N+1)
for i in range(N-1):
    if P[i+1]>P[i]:
        inc[i+1]=1

for i in range(N):
    if inc[i+1]!=0:
        inc[i+1]+=inc[i]

#print(inc)
Un=UnionFind(N-K)
sorted_seg_par=None

for i in range(N-K):
    #start=iとする
    if inc[i+K]>=K-1:#[i,i+K]はsorted
        if sorted_seg_par is None:
            sorted_seg_par=i
        else:
            Un.union(sorted_seg_par,i)
    elif i+1<N-K and P[i]==Seg_min.query(i,i+K+1) and P[i+K+1]>Seg_max.query(i,i+K+1):#[i,i+K]と[i+1,i+K+1]はequivalent
        Un.union(i,i+1)
print(Un.componentNum())

ans=0
for i in range(N-K):
    if i==Un.parent[i]:
        ans+=1
#print(ans)

Submission status: Wrong Answer

Solution code:
# AGC038B
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from queue import deque
from collections import defaultdict
n, k = map(int, input().split())
p = list(map(int, input().split()))

count = 0
q = deque([])
maxq = deque([])
ren = 0
prev = -1
es = defaultdict(set)
slist = []
for i,num in enumerate(p):
    if i>=k:
        m = p[q[0]]
        M = p[maxq[0]]
        if num>M and m==p[i-k]:
            count += 1
            es[i-k].add(i-k+1)
            es[i-k+1].add(i-k)

    if prev<num:
        ren += 1
        prev = num
        if ren>=k-1:
            slist.append(i-k+1)
    else:
        ren = 0
        prev = num
    
    while q and p[q[-1]]>num:
        q.pop()
    q.append(i)
    if q[0]<=i-k:
        q.popleft()
    while maxq and p[maxq[-1]]<num:
        maxq.pop()
    maxq.append(i)
    if maxq[0]<=i-k:
        maxq.popleft()
# if len(slist)>=2:
#     for i in range(len(slist)-1):
#         es[slist[i]].add(slist[i+1])
#         es[slist[i+1]].add(slist[i])
ans = 0   
# seen = [False] * n
# for i in range(n-k+1):
#     if seen[i]:
#         continue
#     ans += 1
#     q = [i]
#     seen[i] = True
#     while q:
#         u = q.pop()
#         for v in es[u]:
#             if not seen[v]:
#                 q.append(v)
#                 seen[v] = True
ans = n - k + 1 - count
if any(item in es for item in slist):
    pass
else:
    ans -= max(len(slist)-1, 0)

print(ans)

Submission status: Wrong Answer

Solution code:
# AGC038B
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from queue import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))

count = 0
q = deque([])
maxq = deque([])
ren = 0
prev = -1
es = []
slist = []
for i,num in enumerate(p):
    if i>=k:
        m = p[q[0]]
        M = p[maxq[0]]
        if num>M and m==p[i-k]:
            count += 1
            es.append((i-k, i-k+1))

    if prev<num:
        ren += 1
        prev = num
        if ren>=k-1:
            slist.append(i-k+1)
    else:
        ren = 0
        prev = num
    
    while q and p[q[-1]]>num:
        q.pop()
    q.append(i)
    if q[0]<=i-k:
        q.popleft()
    while maxq and p[maxq[-1]]<num:
        maxq.pop()
    maxq.append(i)
    if maxq[0]<=i-k:
        maxq.popleft()
# if len(slist)>=2:
#     for i in range(len(slist)-1):
#         es.append((slist[i], slist[i+1]))
# for i in range(n):
ans = n-k+1 - count
if len(slist)>=2:
    ans -= (len(slist) - 1)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from heapq import heappush, heappop
N,K,*P = map(int, open(0).read().split())
i = 0
ans = 1
Cnt = Counter(P[:K])
mls = []
Mls = []
for i in range(K):
  heappush(mls,P[i])
  heappush(Mls,-P[i])
for i in range(N-K):
  Cnt[P[i]] -= 1
  Cnt[P[i+K]] += 1
  if not (P[i]==mls[0] and P[i+K]>=-Mls[0]):
    ans += 1
  heappush(mls,P[i+K])
  heappush(Mls,-P[i+K])
  while Cnt[mls[0]]==0:
    heappop(mls)
  while Cnt[-Mls[0]]==0:
    heappop(Mls)
i = 0
for j in range(1,N):
  if P[j]<P[j-1]:
    if j-i>=K:
      ans -= 1
    i = j
if j-i>=K-1:
  ans -= 1
ans += 1
print(ans)

Submission status: Wrong Answer

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

LIS=[1 for i in range(0,N)]
s=0
t=1
while N>t:
    if P[t]>=P[t-1]:
        t+=1
        if t==N:
            ans=N-s
            while t>s:
                LIS[s]=ans
                s+=1
                ans-=1
    else:
        ans=t-s
        while t>s:
            LIS[s]=ans
            s+=1
            ans-=1
        t+=1

nochange=set([])
for i in range(0,N-K+1):
    if LIS[i]>=K:
        nochange.add(i)

n=N
#セグメント木
#####segfunc######
def segfunc(x,y):
    return (min(x[0],y[0]),max(x[1],y[1]))

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

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

#####単位元######
ide_ele =(10**20,0)

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
PP=[(P[i],P[i]) for i in range(0,N)]
init(PP)
ans=[]
if 0 not in nochange:
    ans.append(0)
for i in range(1,N-K+1):
    if i in nochange:
        continue
    else:
        M=query(i,i+K)[1]
        m=query(i-1,i-1+K)[0]
        if m==P[i-1] and M==P[i+K-1]:
            continue
        else:
            ans.append(i)
print(ans)
if nochange:
    print(len(ans)+1)
else:
    print(len(ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


class BinaryIndexTree:  # 1-indexed
    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


if __name__ == "__main__":
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    P = [p + 1 for p in P]

    bit = BinaryIndexTree(N + 1)
    memo = defaultdict(int)

    swap = 0
    for i in range(K):
        bit.add(P[i], 1)
        swap += i + 1 - bit.sum(P[i])

    ans = 0
    memo[swap] += 1
    for i in range(K, N):
        bit.add(P[i - K], -1)
        sub = bit.sum(P[i - K])
        bit.add(P[i], 1)
        add = K - bit.sum(P[i])
        swap = swap - sub + add
        if add == 0 and sub == 0:
            ans -= 1
        memo[swap] += 1

    for k, v in memo.items():
        if k:
            ans += v
        else:
            ans += 1
    print(ans)

Submission status: Wrong Answer

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

kmin = [0]*(n-k)
kmax = [0]*(n-k)
mq = deque()
Mq = deque()
mq.append((P[0],0))
Mq.append((P[0],0))

cnt = 0
ans = 0
flag = 0
for i in range(1,n):
    if P[i] > P[i-1]:
        cnt += 1
    else:
        ans -= (cnt >= k-1)
        # if cnt >= k:flag = True
        cnt = 0

    while mq and mq[-1][0] > P[i]:
        mq.pop()
    while Mq and Mq[-1][0] < P[i]:
        Mq.pop()
    mq.append((P[i],i))
    Mq.append((P[i],i))
    if i >= k:
        kmin[i-k] = mq[0][0]
        kmax[i-k] = Mq[0][0]
    if mq[0][1] == i-k:
        mq.popleft()
    if Mq[0][1] == i-k:
        Mq.popleft()

# ans += flag
ans += n-k+1

for i in range(n-k):
    if kmin[i] == P[i] and kmax[i] == P[i + k]:
        ans -= 1
print(ans)

Submission status: Wrong Answer

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

kmin = [0]*(n-k)
kmax = [0]*(n-k)
mq = deque()
Mq = deque()
mq.append((P[0],0))
Mq.append((P[0],0))

done = 0
cnt = 0
ans = 0
flag = 0
for i in range(1,n):
    if P[i] > P[i-1]:
        cnt += 1
    else:
        ans -= (cnt >= k-1)
        if cnt >= k:flag = True
        cnt = 0

    while mq and mq[-1][0] > P[i]:
        mq.pop()
    while Mq and Mq[-1][0] < P[i]:
        Mq.pop()
    mq.append((P[i],i))
    Mq.append((P[i],i))
    if i >= k:
        kmin[i-k] = mq[0][0]
        kmax[i-k] = Mq[0][0]
    if mq[0][1] == i-k:
        mq.popleft()
    if Mq[0][1] == i-k:
        Mq.popleft()
ans += flag
ans += n-k+1

for i in range(n-k):
    if kmin[i] == P[i] and kmax[i] == P[i + k]:
        ans -= 1
print(ans)

Submission status: Wrong Answer

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()
    if i >= k - 1:
        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: Wrong Answer

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)
exit(0)
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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
P = list(map(int, input().split()))

INF = 2**31 - 1
N0 = 1 << (n-1).bit_length()
seg_min = [INF]*(N0 << 1)
seg_max = [0]*(N0 << 1)

def update_min(i, x):
    i += N0
    seg_min[i] = x
    while i > 1:
        y = seg_min[i ^ 1]
        if y <= x:
            break
        i >>= 1
        seg_min[i] = x
            
def query_min(l, r):
    res = INF
    l += N0
    r += N0
    while l < r:
        if r & 1:
            res = min(res, seg_min[r-1])
        if l & 1:
            res = min(res, seg_min[l])
            l += 1
        l >>= 1
        r >>= 1
 
    return res

def init_min(original):
    for i, x in enumerate(original):
        update_min(i, x)
        
def update_max(i, x):
    i += N0
    seg_max[i] = x
    while i > 1:
        y = seg_max[i ^ 1]
        if y >= x:
            break
        i >>= 1
        seg_max[i] = x
            
def query_max(l, r):
    res = 0
    l += N0
    r += N0
    while l < r:
        if r & 1:
            res = max(res, seg_max[r-1])
        if l & 1:
            res = max(res, seg_max[l])
            l += 1
        l >>= 1
        r >>= 1
 
    return res

def init_max(original):
    for i, x in enumerate(original):
        update_max(i, x)
        
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 unite(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())

init_min(P)
init_max(P)

uf = UnionFind(n-k+1)

for i in range(n-k):
  m = query_min(i, i+k+1)
  M = query_max(i, i+k+1)
  if m == P[i] and M == P[i+k]:
    uf.unite(i, i+1)

q = -1
s = 0
for i in range(k-1):
  if P[i] < P[i+1]:
    s += 1
if s == k-1:
  q = 0
for i in range(n-k-1):
  s -= int(P[i] < P[i+1])
  s += int(P[i+k] < P[i+k+1])
  if s == k-1:
    if q == -1:
      q = i
    else:
      uf.unite(q, i)
ans = uf.group_count()
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
P = list(map(int, input().split()))
mn = [N] * (N-K)
mx = [-1] * (N-K)
min_heap = []
max_heap = []
for i in range(K):
    heappush(min_heap, P[i])
    heappush(max_heap, -P[i])
used = set()
for i in range(N-K):
    heappush(min_heap, P[i+K])
    heappush(max_heap, -P[i+K])
    while min_heap[0] in used:
        heappop(min_heap)
    while -max_heap[0] in used:
        heappop(max_heap)
    mn[i] = min_heap[0]
    mx[i] = -max_heap[0]
    used.add(P[i])
ans = 1
for i in range(N-K):
    if P[i] != mn[i] or P[i+K] != mx[i]:
        ans += 1
inc = 1
cnt = 0
for i in range(1, N):
    if P[i-1] < P[i]:
        inc += 1
    else:
        inc = 1
    if inc >= K:
        cnt += 1
ans -= max(0, cnt-1)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
if N == K:
    print(1)
    exit()
P = list(map(int, input().split()))
P.append(-1)
mn = [N] * (N-K)
mx = [-1] * (N-K)
min_heap = []
max_heap = []
for i in range(K):
    heappush(min_heap, P[i])
    heappush(max_heap, -P[i])
used = set()
for i in range(N-K):
    while min_heap[0] in used:
        heappop(min_heap)
    while -max_heap[0] in used:
        heappop(max_heap)
    mn[i] = min_heap[0]
    mx[i] = -max_heap[0]
    used.add(P[i])
    heappush(min_heap, P[i+K+1])
    heappush(max_heap, -P[i+K+1])
ans = 0
for i in range(N-K):
    if P[i] != mn[i] or P[i+K] != mx[i]:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

class RMQ:
    def __init__(self, size):
        n = 1
        while n < size:
            n <<= 1
        self.n = n
        self.data = [float('inf')]*(2*n-1)

    # change the value of the ith element to x
    def update(self, i, x):
        i += self.n-1  # the leaf
        self.data[i] = x
        while i > 0:
            i = (i-1)//2
            self.data[i] = min(self.data[i*2+1], self.data[i*2+2])

    # return the minimum value in the range [a, b)
    # i is the index of the node, and it corresponds to the range [l, r)
    def query(self, a, b, i=0, l=0, r=-1):
        if r == -1:
            r = self.n

        # if no overlap
        if r <= a or b <= l:
            return float('inf')

        # if [a, b) contains whole [l, r)
        if a <= l and r <= b:
            return self.data[i]
        else:
            m = (l+r)//2
            vl = self.query(a, b, i*2+1, l, m)
            vr = self.query(a, b, i*2+2, m, r)
            return min(vl, vr)

N, K = map(int, input().split())
P = list(map(int, input().split()))
rmq_min = RMQ(N)
rmq_max = RMQ(N)
for i in range(N):
    rmq_min.update(i, P[i])
    rmq_max.update(i, -P[i])

ans = 1
for i in range(N-K-1):
    if P[i] != rmq_min.query(i, i+K+1) or P[i+K+1] != -rmq_max.query(i, i+K+1):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k = map(int,input().split())
a = list(map(int,input().split()))
k -= 1
mnlist = []
q = deque([0])
for i in range(1,k):
  while q:
    x = q.pop()
    if a[i]>a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)

for i in range(k,n+1):
  t = q.popleft()
  mnlist.append(a[t])
  if t != i-k:
    q.appendleft(t)
  if i == n:
    break
  while q:
    x = q.pop()
    if a[i]>a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)
mxlist = []
q = deque([0])
for i in range(1,k):
  while q:
    x = q.pop()
    if a[i]<a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)

for i in range(k,n+1):
  t = q.popleft()
  mxlist.append(a[t])
  if t != i-k:
    q.appendleft(t)
  if i == n:
    break
  while q:
    x = q.pop()
    if a[i]<a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)
ans = n-k
r = set()
for i in range(1,n-k):
  if a[i-1]<mnlist[i] and mxlist[i]<a[i+k]:
    r.add(i)
flg = 0
flg2 = 0
for i in range(1,n-k):
  if a[i-1] < a[i]:
    flg += 1
  else:
    flg = 0
  if flg >= k:
    r.add(i-k)
    flg2 = 1
print(ans-len(r)+flg2)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k = map(int,input().split())
a = list(map(int,input().split()))
k -= 1
mnlist = []
q = deque([0])
for i in range(1,k):
  while q:
    x = q.pop()
    if a[i]>a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)

for i in range(k,n+1):
  t = q.popleft()
  mnlist.append(a[t])
  if t != i-k:
    q.appendleft(t)
  if i == n:
    break
  while q:
    x = q.pop()
    if a[i]>a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)
mxlist = []
q = deque([0])
for i in range(1,k):
  while q:
    x = q.pop()
    if a[i]<a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)

for i in range(k,n+1):
  t = q.popleft()
  mxlist.append(a[t])
  if t != i-k:
    q.appendleft(t)
  if i == n:
    break
  while q:
    x = q.pop()
    if a[i]<a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)
ans = n-k
r = set()
for i in range(1,n-k):
  if a[i-1]<mnlist[i] and mxlist[i]<a[i+k]:
    r.add(i)
flg = 0
for i in range(1,n-k):
  if a[i-1] < a[i]:
    flg += 1
  else:
    flg = 0
  if flg >= k:
    r.add(i-k)
print(max(1,ans-len(r)))

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k = map(int,input().split())
a = list(map(int,input().split()))
k -= 1
mnlist = []
q = deque([0])
for i in range(1,k):
  while q:
    x = q.pop()
    if a[i]>a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)

for i in range(k,n+1):
  t = q.popleft()
  mnlist.append(a[t])
  if t != i-k:
    q.appendleft(t)
  if i == n:
    break
  while q:
    x = q.pop()
    if a[i]>a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)
mxlist = []
q = deque([0])
for i in range(1,k):
  while q:
    x = q.pop()
    if a[i]<a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)

for i in range(k,n+1):
  t = q.popleft()
  mxlist.append(a[t])
  if t != i-k:
    q.appendleft(t)
  if i == n:
    break
  while q:
    x = q.pop()
    if a[i]<a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)
ans = n-k
r = set()
for i in range(1,n-k):
  if a[i-1]<mnlist[i] and mxlist[i]<a[i+k]:
    r.add(i)
flg = 0
for i in range(1,n-k):
  if a[i-1] < a[i]:
    flg += 1
  else:
    flg = 0
  if flg >= k:
    r.add(i-k)
print(ans-len(r))

Submission status: Wrong Answer

Solution code:
class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res

    def add(self, index, x):
        while index <= self.n:
            self.tree[index] += x
            index += index & -index

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1


N, K = map(int, input().split())
P = list(map(lambda x: int(x) + 1, input().split()))

bit = BinaryIndexedTree(N + 1)
count = 1

for i in range(K):
    bit.add(P[i], 1)

for i in range(N - K):
    mi = bit.bisect_left(1)
    ma = bit.bisect_left(K)
    if P[i] != mi or P[K + i] < ma:
        count += 1
    bit.add(P[i], -1)
    bit.add(P[K + i], 1)

inc = 0
incl = 1

for i in range(N - 1):
    if P[i] < P[i + 1]:
        incl += 1
    else:
        inc += max(0, incl - K + 1)
        incl = 1

inc += max(0, incl - K + 1)

print(count - max(0, inc - 1))

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
p=[]
s=l[0]
e=l[k-1]
ans=1
for i in range(n-k):
    if not (l[i]<l[i+1] and l[i+k-1]<l[i+k]):
        ans+=1
    elif l[i+1]>l[i+k]:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
p=[]
s=l[0]
e=l[k-1]
ans=1
for i in range(n-k):
    if not (l[i]<l[i+1] and l[i+k-1]<l[i+k]):
        ans+=1
print(ans)