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:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def twopowerceil(n):  # return m s.t. m>=n and m=2**p
    for i in range(40):
        m = 2**i
        if m >= n:
            return m
    return -1

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

def segtreemininit(a,n):  # upto N-1, not N
    global mintree,maxtree
    nn = twopowerceil(n)
    mintree = [BIG]*(2*nn)
    for i in range(n):
        mintree[nn-1+i] = a[i]
    for i in range(nn-2,-1,-1):
        mintree[i] = min(mintree[2*i+1], mintree[2*i+2])

def segtreemin(x,y,n):
    nn = twopowerceil(n)
    return segtreemincore(x,y,0,0,nn)

def segtreemincore(x,y,k,l,r):
    if r<=x or y<=l:
        return BIG
    if x<=l and r<=y:
        return mintree[k]
    vl = segtreemincore(x,y,2*k+1,l,(l+r)//2)
    vr = segtreemincore(x,y,2*k+2,(l+r)//2,r)
    return min(vl,vr)

# # # #

def segtreemaxinit(a,n):  # upto N-1, not N
    global maxtree
    nn = twopowerceil(n)
    maxtree = [-BIG]*(2*nn)
    for i in range(n):
        maxtree[nn-1+i] = a[i]
    for i in range(nn-2,-1,-1):
        maxtree[i] = max(maxtree[2*i+1], maxtree[2*i+2])

def segtreemax(x,y,n):
    nn = twopowerceil(n)
    return segtreemaxcore(x,y,0,0,nn)

def segtreemaxcore(x,y,k,l,r):
    if r<=x or y<=l:
        return -BIG
    if x<=l and r<=y:
        return maxtree[k]
    vl = segtreemaxcore(x,y,2*k+1,l,(l+r)//2)
    vr = segtreemaxcore(x,y,2*k+2,(l+r)//2,r)
    return max(vl,vr)


n,k = inm()
a = inl()

segtreemininit(a,n)
segtreemaxinit(a,n)

st = 1
kstrkscnt = 0
kstrks = [False]*n
for i in range(n-1):
    if a[i]<a[i+1]:
        st += 1
        if st>=k:
            kstrkscnt += 1
            kstrks[i+1] = True
    else:
        st = 1

cnt = 0
for i in range(n-k):
    if not kstrks[i+k-1] and a[i]<segtreemin(i+1,i+k-1,n) \
       and segtreemax(i+1,i+k-1,n)<a[i+k]:
       cnt += 1

if kstrkscnt>0:
    kstrkscnt -= 1
print(n-k+1-kstrkscnt-cnt)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
P = np.array(lr())
up = (P[1:] - P[:-1]) > 0
answer = N - K
up_cum = np.cumsum(up)
diff = (up_cum[K:] - up_cum[:-K]) == K
answer -= min(N-K-1, diff.sum())
print(answer)
# 04

Submission status: Wrong Answer

Solution code:
def init(N, L):
    i = 1
    d = 0
    while i < N:
        i <<= 1
        d += 1
    segTree = [[10000000, 0] for _ in range(2 * i - 1)]
    for j, l in enumerate(L):
        now = i - 1 + j
        segTree[now] = [l, l]
        for _ in range(d):
            segTree[(now - 1) >> 1][0] = min(segTree[(now - 1) >> 1][0], segTree[now][0])
            segTree[(now - 1) >> 1][1] = max(segTree[(now - 1) >> 1][1], segTree[now][1])
            now = (now - 1) >> 1

    return segTree, i, d 

def search_min(l, r, nowl, nowr, k, segTree): #[l, r)の最小値を返す。
    if l <= nowl and nowr <= r: return segTree[k][0]
    if nowr <= l or r <= nowl: return 10000000
    left = search_min(l, r, nowl, (nowl + nowr) >> 1, (k << 1) + 1, segTree)
    right = search_min(l, r, (nowl + nowr) >> 1, nowr, (k << 1) + 1, segTree)
    return min(left, right)

def search_max(l, r, nowl, nowr, k, segTree):
    if l <= nowl and nowr <= r: return segTree[k][1]
    if nowr <= l or r <= nowl: return 0
    left = search_max(l, r, nowl, (nowl + nowr) >> 1, (k << 1) + 1, segTree)
    right = search_max(l, r, (nowl + nowr) >> 1, nowr, (k << 1) + 1, segTree)
    return max(left, right)

def solve():
    N, K = map(int, input().split())
    P = [int(p) for p in input().split()]
    segTree, di, d = init(N, P)
    order = [0] * N
    for i in range(1, N):
        if P[i] > P[i-1]: order[i] = order[i-1] + 1

    count = 1
    same = False
    for i in range(1, N - K + 1):
        if same and order[i + K - 1] > K - 1: continue
        elif not same and order[i + K - 1] > K - 1: same = True
        oldmin = search_min(i-1, i-1+K, 0, di, 0, segTree)
        oldmax = search_max(i-1, i-1+K, 0, di, 0, segTree)
        #print(oldmin, oldmax)
        if P[i-1] == oldmin and oldmax < P[i + K - 1]: continue
        count += 1

 
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def init(N, L):
    i = 1
    d = 0
    while i < N:
        i <<= 1
        d += 1
    segTree = [[10000000, 0] for _ in range(2 * i - 1)]
    for j, l in enumerate(L):
        now = i - 1 + j
        segTree[now] = [l, l]
        for _ in range(d):
            segTree[(now - 1) // 2][0] = min(segTree[(now - 1) // 2][0], segTree[now][0])
            segTree[(now - 1) // 2][1] = max(segTree[(now - 1) // 2][1], segTree[now][1])
            now = (now - 1) // 2

    return segTree, i, d 

def search_min(l, r, nowl, nowr, k, segTree): #[l, r)の最小値を返す。
    if l <= nowl and nowr <= r: return segTree[k][0]
    if nowr <= l or r <= nowl: return 10000000
    left = search_min(l, r, nowl, (nowl + nowr) // 2, 2 * k + 1, segTree)
    right = search_min(l, r, (nowl + nowr) // 2, nowr, 2 * k + 2, segTree)
    return min(left, right)

def search_max(l, r, nowl, nowr, k, segTree):
    if l <= nowl and nowr <= r: return segTree[k][1]
    if nowr <= l or r <= nowl: return 0
    left = search_max(l, r, nowl, (nowl + nowr) // 2, 2 * k + 1, segTree)
    right = search_max(l, r, (nowl + nowr) // 2, nowr, 2 * k + 2, segTree)
    return max(left, right)

def solve():
    N, K = map(int, input().split())
    P = [int(p) for p in input().split()]
    segTree, di, d = init(N, P)
    order = [0] * N
    same = 0
    for i in range(1, N):
        if P[i] > P[i-1]: order[i] = order[i-1] + 1
        if order[i] >= K - 1: same += 1

    count = 1
    for i in range(1, N - K + 1):
        oldmin = search_min(i-1, i-1+K, 0, di, 0, segTree)
        oldmax = search_max(i-1, i-1+K, 0, di, 0, segTree)
        #print(oldmin, oldmax)
        if P[i-1] == oldmin and oldmax < P[i + K - 1]: continue
        count += 1

    if same > 0: count -= same - 1
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class SegmentTree:
  def __init__(self, size, default, op = max):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

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

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

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

STmin = SegmentTree(N,0,min)
STmax = SegmentTree(N,0,max)
for i in range(N):
  STmin.update(i,P[i])
  STmax.update(i,P[i])
ans = 1
for i in range(1,N-K+1):
  #print(i-1,i,i+K-2,i+K-1)
  if STmin.get(i-1,i+K-1) != P[i-1] or STmax.get(i,i+K) != P[i+K-1]:
    ans += 1

cnt = 0
for i in range(N-K+1):
  if P[i:i+K] == sorted(P[i:i+K]):
    cnt += 1
#print(cnt)
if cnt > 1:
  ans -= (cnt-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N, K = rl()
P = rl()
q = []

for i in range(K):
    q.append(i)
answer = 1
for i in range(N-K):
    x = q.pop(0)
    y = P[i+K]
    if not (x < min(q) and y > max(q)):
        answer += 1
    q.append(y)

print(answer)
# 56

Submission status: Wrong Answer

Solution code:
class SegmentTree:
  def __init__(self, size, default, op = max):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

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

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

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

STmin = SegmentTree(N,0,min)
STmax = SegmentTree(N,0,max)
for i in range(N):
  STmin.update(i,P[i])
  STmax.update(i,P[i])
ans = 1
for i in range(2,N-K+1):
  if STmin.get(i-1,i-1+K) != P[i-1] or STmax.get(i,i+K) != P[i+K-1]:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

dec = [0]

for i in range(1,n):
    if p[i-1]>p[i]:
        dec.append(i)
ans = 1
for i in range(1,len(dec)):
    s1 = dec[i-1]
    s2 = dec[i]-1
    e1 = s1+k
    e2 = s2+k
    ans += bisect.bisect_left(dec,e2)-bisect.bisect_left(dec,e1)+1

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

class SparseTable(object):
    def __init__(self,A):
        n=len(A)
        logn=max(0,(n-1).bit_length())
        maxtable=[[0]*n for _ in range(logn)]
        maxtable[0]=A[:]
        mintable=[[0]*n for _ in range(logn)]
        mintable[0]=A[:]
        from itertools import product
        for i,k in product(range(1,logn),range(n)):
            if(k+(1<<(i-1))>=n):
                maxtable[i][k]=maxtable[i-1][k]
                mintable[i][k]=mintable[i-1][k]
            else:
                maxtable[i][k]=max(maxtable[i-1][k],maxtable[i-1][k+(1<<(i-1))])
                mintable[i][k]=min(mintable[i-1][k],mintable[i-1][k+(1<<(i-1))])
        self.__n=n
        self.__maxtable=maxtable
        self.__mintable=mintable

    def max(self,l,r):
        n=self.__n
        assert 0<=l<r<=n
        i=max(0,(r-l-1).bit_length()-1)
        maxtable=self.__maxtable
        return max(maxtable[i][l],maxtable[i][r-(1<<i)])

    def min(self,l,r):
        n=self.__n
        assert 0<=l<r<=n
        i=max(0,(r-l-1).bit_length()-1)
        mintable=self.__mintable
        return min(mintable[i][l],mintable[i][r-(1<<i)])

def resolve():
    n,k=map(int,input().split())
    P=list(map(int,input().split()))
    table=SparseTable(P)
    ans=n-k+1
    for i in range(n-k):
        m=table.min(i,i+k)
        M=table.max(i+1,i+1+k)
        if(m==P[i] and M==P[i+k]):
            ans-=1

    cnt=0
    num=0
    P.append(-1) # 番兵
    for i in range(n):
        if(P[i+1]>P[i]):
            cnt+=1
        else:
            num+=max(cnt-k+2,0)
            cnt=0
    ans-=max(num-1,0)
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
INF = 10**30

class Rmax():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [-INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = max(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = -INF
		while L<R:
			if R & 1:
				R -= 1
				s = max(s, self.node[R-1])
			if L & 1:
				s = max(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, k = map(int, input().split())
p = list(map(int, input().split()))
ma, mi = Rmax(n), Rmin(n)
for i in range(n):
	ma.Update(i, p[i])
	mi.Update(i, p[i])
ans = n-k+1
tmp, cnt = 0, 0
for i in range(1, n):
	if p[i-1] < p[i]:
		tmp += 1
	else:
		tmp = 0
	if tmp >= k-1:
		cnt += 1
ans -= max(0, cnt-1)
for i in range(k, n):
	if p[i-k] < mi.Get(i-k+1, i) and ma.Get(i-k+1, i) < p[i]:
		ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N,K = map(int, input().split())
P = [int(p) for p in input().split()]

L = [0]*(N-1)
for i in range(N-1):
    if P[i] > P[i+1]:
        L[i] = 1
        
ans = 0
h = []
for i in range(K-1):
    heapq.heappush(h, (-P[i], i))
    
cnt = sum(L[:K-1])
if cnt == 0:
    f = 1
else:
    f = 0
    ans += 1
    
for i in range(N-K):
    cnt += L[i+K-1] - L[i]
    if L[i] == 1 or L[i+K-1] == 1:
        if cnt > 0:
            ans += 1
    else:
        while h[0][1] <= i:
            heapq.heappop(h)
        if -h[0][0] > P[i+K]:
            ans += 1
    heapq.heappush(h, (-P[i+K], i+K))
    if cnt == 0:
        f = 1
            
        
print(ans+f)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
P = [int(p) for p in input().split()]

L = [0]*(N-1)
for i in range(N-1):
    if P[i] > P[i+1]:
        L[i] = 1
        
ans = 1
        
for i in range(N-K):
    if L[i] == 1 or L[i+K-1] == 1:
        ans += 1
        
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
P = [int(p) for p in input().split()]

l = 0
r = 0
memo = []
while r+1 < N:
    if P[r] < P[r+1]:
        r += 1
    else:
        l = r+1
        r += 1
    if r-l+1 == K:
        memo.append(l)
        l += 1
        
L = [0]*(N-1)
for i in range(N-1):
    if P[i] > P[i+1]:
        L[i] += 1
        
if len(memo) > 0 and memo[0] == 0:
    ans = 0
else:
    ans = 1
    
f = 0
for i in range(N-K):
    if L[i] == 1 or L[i+K-1] == 1:
        ans += 1
        if len(memo) > 0 and memo[0] == i:
            f += 1
            memo.pop()
            
if len(memo) > 0 and f == 0:
    ans += 1
elif f > 0:
    ans -= f
    ans += 1

            
print(ans)

Submission status: Wrong Answer

Solution code:
# instead of AVLTree
class BITbisect():
    def __init__(self, max):
        self.max = max
        self.data = [0]*(self.max+1)
    
    # 0からiまでの区間和
    # 立っているビットを下から処理
    def query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # i番目の要素にxを足す
    # 覆ってる区間すべてに足す
    def add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i

    def insert(self, x):
        self.add(x, 1)

    def delete(self, x):
        self.add(x, -1)

    def count(self, x):
        return self.query_sum(x) - self.query_sum(x-1)
    
    def length(self):
        return self.query_sum(self.max)
    
    # 下からc番目(0-indexed)の数
    # O(log(N))
    def search(self, c):
        c += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < c:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        if ind == self.max:
            return False
        return ind + 1
    
    def bisect_right(self, x):
        return self.query_sum(x)

    def bisect_left(self, x):
        if x == 1:
            return 0
        return self.query_sum(x-1)

    # listみたいに表示
    def display(self):
        print('inside BIT:', end=' ')
        for x in range(1, self.max+1):
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    print(x, end=' ')
        print()
    
import sys
input = sys.stdin.readline

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

bit = BITbisect(N)

for i in range(K):
    bit.insert(A[i]+1)

ans = 1
for i in range(K, N):
    if A[i-K]+1 != bit.search(0) or A[i]+1 <= bit.search(K-1):
        ans += 1
    bit.delete(A[i-K]+1)
    bit.insert(A[i]+1)

c = 1
p = 0
for i in range(N-1):
    if A[i] < A[i+1]:
        c += 1
    else:
        p += max(0, c-K+1)
        c = 1
p += max(0, c-K+1)

ans -= max(p-1, 0)

print(ans)

Submission status: Wrong Answer

Solution code:
class SWAG():
    def __init__(self,unit,f):
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        self.f=f
    def __refill_right(self):
        for _ in range(len(self.data_l)//2):
            self.append(self.popleft())
    def __refill_left(self):
        for _ in range(len(self.data_r)//2):
            self.appendleft(self.pop())
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__refill_right()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__refill_left()
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min)
s_max=SWAG(0,max)
*_,=map(s_min.append,p[:k-1])
*_,=map(s_max.append,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Submission status: Wrong Answer

Solution code:
class SWAG():
    def __init__(self,unit,f):
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        self.f=f
    def __refill_right(self):
        for _ in range(len(self.data_l)//2):
            self.append(self.popleft())
    def __refill_left(self):
        for _ in range(len(self.data_r)//2):
            self.appendleft(self.pop())
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__refill_right()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__refill_left()
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min)
s_max=SWAG(0,max)
*_,=map(s_min.append,p[:-1])
*_,=map(s_max.append,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Submission status: Wrong Answer

Solution code:
class SWAG():
    def __init__(self,unit,f):
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        self.f=f
    def __refill_right(self):
        for _ in range(len(self.data_l)//2):
            self.append(self.popleft())
    def __refill_left(self):
        for _ in range(len(self.data_r)//2):
            self.appendleft(self.pop())
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__refill_right()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__refill_left()
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min)
s_max=SWAG(0,max)
*_,=map(s_min.append,p[:k-1])
*_,=map(s_max.append,p[1:k])
for i,(a,b,c,d)in enumerate(zip(p,p[k:],c,p[k-1:])):
    f|=c
    s_min.append(d)
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, K = map(int, input().split())
P = [int(i) for i in input().split()]

ma = []
mi = []

for i in range(K) :
    heappush(ma, (-P[i], i))
    heappush(mi, (P[i], i))

ret = 1
for i in range(K, N) :
    heappush(ma, (-P[i], i))
    heappush(mi, (P[i], i))
    
    while ma[0][1] < i - K :
        heappop(ma)
    while mi[0][1] < i - K :
        heappop(mi)
        
    if P[i-K] != mi[0][0] or P[i] != -ma[0][0] :
        ret += 1

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

over = sum([dp[i] >= K for i in range(N)])

print(max(1, ret - max(0, over - 1)))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, K = map(int, input().split())
P = [int(i) for i in input().split()]

ma = []
mi = []

for i in range(K) :
    heappush(ma, (-P[i], i))
    heappush(mi, (P[i], i))

ret = 1
for i in range(K, N) :
    heappush(ma, (-P[i], i))
    heappush(mi, (P[i], i))
    
    while ma[0][1] < i - K :
        heappop(ma)
    while mi[0][1] < i - K :
        heappop(mi)
        
    if P[i-K] != mi[0][0] or P[i] != -ma[0][0] :
        ret += 1

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

over = sum([dp[i] >= K for i in range(N)])

if dp[K-1] == K :
    ret += 1

print(ret - max(0, over - 1))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, K = map(int, input().split())
P = [int(i) for i in input().split()]

ma = []
mi = []

for i in range(K) :
    heappush(ma, (-P[i], i))
    heappush(mi, (P[i], i))

ret = 1
for i in range(K, N) :
    heappush(ma, (-P[i], i))
    heappush(mi, (P[i], i))
    
    while ma[0][1] < i - K :
        heappop(ma)
    while mi[0][1] < i - K :
        heappop(mi)
        
    if P[i-K] != mi[0][0] or P[i] != -ma[0][0] :
        ret += 1

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

over = sum([dp[i] >= K for i in range(N)])
        
print(ret - max(0, over - 1))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, P):
    hmax = []
    hmin = []
    for i in range(K):
        heapq.heappush(hmax, -P[i])
        heapq.heappush(hmin, P[i])
    
    a = []
    for p0, p1 in zip(P, P[1:]):
        a.append(1 if p1 > p0 else -1)
    
    sa = [0]
    for b in a:
        sa.append(sa[-1] + b)

    ans = 1
    used = set()
    for i in range(N-K):
        l = P[i]
        r = P[i+K]
        heapq.heappush(hmax, -r)
        if l != hmin[0] or r != -hmax[0]:
            if sa[i+K-1] - sa[i] != K-1:
                ans += 1

        heapq.heappush(hmin, r)
        used.add(l)
        while hmin[0] in used:
            heapq.heappop(hmin)
        while -hmax[0] in used:
            heapq.heappop(hmax)

    return ans 


def main():
    N, K = read_int_n()
    P = read_int_n()
    print(slv(N, K, P))

    # N = 200000
    # K = random.randint(1, N-1)
    # P = list(range(N))
    # random.shuffle(P)

    # N = 5
    # K = 2
    # P = [2,4, 0, 3, 1]
    # print(N, K)
    # print(' '.join(map(str, P)))

    # print(slv(N, K, P))
    


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, P):
    hmax = []
    hmin = []
    for i in range(K):
        heapq.heappush(hmax, -P[i])
        heapq.heappush(hmin, P[i])
    
    a = []
    for p0, p1 in zip(P, P[1:]):
        a.append(1 if p1 > p0 else -1)
    
    sa = [0]
    for b in a:
        sa.append(sa[-1] + b)


    ss = 0
    for i in range(N-K+1):
        if sa[i+K-1] - sa[i] == K-1:
            ss += 1
    
    ans = 1
    used = set()
    for i in range(N-K):
        l = P[i]
        r = P[i+K]
        heapq.heappush(hmax, -r)
        if l != hmin[0] or r != -hmax[0]:
            ans += 1

        heapq.heappush(hmin, r)
        used.add(l)
        while hmin[0] in used:
            heapq.heappop(hmin)
        while -hmax[0] in used:
            heapq.heappop(hmax)

    if ss > 0:
        ans -= ss - 1

    return ans 


def main():
    N, K = read_int_n()
    P = read_int_n()
    print(slv(N, K, P))

    # N = 200000
    # K = random.randint(1, N-1)
    # P = list(range(N))
    # random.shuffle(P)

    # N = 5
    # K = 2
    # P = [2,4, 0, 3, 1]
    # print(N, K)
    # print(' '.join(map(str, P)))

    # print(slv(N, K, P))
    


if __name__ == '__main__':
    main()