Problem:


Score : 700 points

Problem Statement

Snuke has a permutation (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1).

Now, he will perform the following operation exactly once:

Choose K consecutive elements in P and sort them in ascending order.

Find the number of permutations that can be produced as P after the operation.

Constraints

2 \leq N \leq 200000

2 \leq K \leq N

0 \leq P_i \leq N-1

P_0,P_1,\cdots,P_{N-1} are all different.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_0 P_1 \cdots P_{N-1}

Output

Print the number of permutations that can be produced as P after the operation.

Sample Input 1

5 3
0 2 1 4 3

Sample Output 1

2

Two permutations can be produced as P after the operation: (0,1,2,4,3) and (0,2,1,3,4).

Sample Input 2

4 4
0 1 2 3

Sample Output 2

1

Sample Input 3

10 4
2 0 1 3 7 5 4 6 8 9

Sample Output 3

6



Sample input:
5 3
0 2 1 4 3


Sample output:
2

Submission status: Accepted

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

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n = 2 ** (n-1).bit_length()
        self.data = [ide] * (self.n*2)
        self.func, self.ide = func, ide
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.n
        self.data[i] = x
        while i > 1:
            i //= 2
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.n; r += self.n 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l //= 2; r //= 2
        return res
    
    def get(self, i):
        return self.data[self.n + i]

minst, maxst = SegmentTree(n), SegmentTree(n, lambda x, y: max(x, y), -float("inf"))
minst.build(p)
maxst.build(p)

ans = n - k + 1
for i in range(n-k):
    j = i + k
    if minst.query(i, j+1) == p[i] and maxst.query(i, j+1) == p[j]:
        ans -= 1

srted = [1] * n
cnt = 0
for i in range(n):
    if p[i] > p[i-1]: srted[i] = srted[i-1] + 1
    if srted[i] == k: cnt += 1

if cnt > 1: ans -= cnt - 1

print(ans)

Submission status: Accepted

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

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

cum_asc = [0]
for p,q in zip(P,P[1:]):
    cum_asc.append(cum_asc[-1] + int(p<q))
all_asc = []
for i in range(N-K+1):
    all_asc.append(cum_asc[i+K-1] - cum_asc[i] == K-1)

from collections import deque
sldmin = []
sldmax = []
qmin = deque()
qmax = deque()
for i,p in enumerate(P):
    while qmin and qmin[-1] > p:
        qmin.pop()
    qmin.append(p)
    if i-K-1 >= 0 and P[i-K-1] == qmin[0]:
        qmin.popleft()
    while qmax and qmax[-1] < p:
        qmax.pop()
    qmax.append(p)
    if i-K-1 >= 0 and P[i-K-1] == qmax[0]:
        qmax.popleft()
    if i >= K:
        sldmin.append(qmin[0])
        sldmax.append(qmax[0])

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1
    def components(self):
        return len(self.parent) - self.count

uf = UnionFind(N-K+2)
for i,(l,r,mn,mx) in enumerate(zip(P,P[K:],sldmin,sldmax)):
    if l==mn and r==mx:
        uf.unite(i,i+1)
if all(f == False for f in all_asc):
    print(uf.components() - 1)
    exit()

def_i = N-K+1 #same as default P
for i,f in enumerate(all_asc):
    if f:
        uf.unite(i, def_i)
print(uf.components())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int,input().split())
P = list(map(int,input().split()))
count = 0
first = 1
def init(init_val,n):
    #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 segfunc(x,y):
    return max([x,y])

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 = 0

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg=[ide_ele]*2*num

def init2(init_val,n):
    #set_val
    for i in range(n):
        seg2[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg2[i]=segfunc2(seg2[2*i+1],seg2[2*i+2])

def segfunc2(x,y):
    return min([x,y])

def update2(k,x):
    k += num-1
    seg2[k] = x
    while k:
        k = (k-1)//2
        seg2[k] = segfunc2(seg2[k*2+1],seg2[k*2+2])

def query2(p,q):
    if q<=p:
        return ide_ele2
    p += num-1
    q += num-2
    res=ide_ele2
    while q-p>1:
        if p&1 == 0:
            res = segfunc2(res,seg2[p])
        if q&1 == 1:
            res = segfunc2(res,seg2[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc2(res,seg2[p])
    else:
        res = segfunc2(segfunc2(res,seg2[p]),seg2[q])
    return res

#####単位元######
ide_ele2 = 10**9

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg2=[ide_ele2]*2*num

l = [0]*(N-1)
for i in range(len(l)):
    if P[i]>=P[i+1]:
        l[i] = 1
l2 = [0]*(N-K+1)
tmp = sum(l[0:K-1])
for i in range(N-K+1):
    if tmp==0:
        l2[i]=1
    if i != N-K:
        tmp += (l[i+K-1]-l[i])
init(P,N)
init2(P,N)
for i in range(N-K+1):
    if l2[i]==1:
        if first == 1:
            count += 1
            first = 0
        continue
    elif  (P[i-1] < query2(i,i+K-1)) and (P[i+K-1] > query(i,i+K-1)) and (i!=0):
        continue
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class SegTree:
    """
    セグメント木
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        # 初期化の値が決まっている場合
        if A:
            # 1段目(最下段)の初期化
            for i in range(n):
                self.tree[n2+i] = A[i]
            # 2段目以降の初期化
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

N, K = MAP()
A = LIST()

# 隣り合う区間との関係を確認(これで重なる区間同士は全てカバーできる)
stmin = SegTree(N, min, INF, A)
stmax = SegTree(N, max, -INF, A)
total = N - K + 1
dup = 0
for i in range(N-K):
    mn = stmin.query(i, i+K+1)
    mx = stmax.query(i, i+K+1)
    if mn == A[i] and mx == A[i+K]:
        dup += 1

# 離れた区間同士の確認
B = [0] * N
for i in range(N-1):
    # 増加か減少で2値化して累積和
    if A[i] < A[i+1]:
        B[i+1] = 1
B = list(accumulate(B))
# 最初の1回は重複にならないのでINFにしておく
prev = INF
for i in range(N-K+1):
    # 増加がK-1回連続している箇所を確認
    if B[i+K-1] - B[i] == K - 1:
        # 前回の該当箇所と離れている(区間が重ならない)ならカウントする
        if prev + K - 1 < i:
            dup += 1
        prev = i

print(total - dup)

Submission status: Accepted

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+=(cnt>=k-1)
            cnt=0
    ans-=max(num-1,0)
    print(ans)
resolve()

Submission status: Accepted

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
same = set()
tmp = 0
for i in range(1, n):
	if p[i-1] < p[i]:
		tmp += 1
	else:
		tmp = 0
	if tmp >= k-1:
		same.add(i-k+1)
ans -= max(0, len(same)-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]:
		if not i-k in same and not i-k+1 in same:
			ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

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:
        if c >= K:
            p += 1
        c = 1
if c >= K:
    p += 1

ans -= max(p-1, 0)

print(ans)

Submission status: Accepted

Solution code:
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=[self.unit]
        self.fold_l=[self.unit]
        self.data_r=[]
        self.data_l=[]
        sep=0--len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    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.construct(self.data_l[::-1])
        if not self.data_r:
            return self.popleft()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(self.data_r)
        if not self.data_l:
            return False
        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,p[:k-1])
s_max=SWAG(0,max,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: Accepted

Solution code:
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=[self.unit]
        self.fold_l=[self.unit]
        self.data_r=[]
        self.data_l=[]
        sep=0--len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    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.construct(self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(self.data_r)
        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,p[:k-1])
s_max=SWAG(0,max,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: Accepted

Solution code:
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=[self.unit]
        self.fold_l=[self.unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        for t in data[sep+1:]:
            self.append(t)
        for t in data[sep::-1]:
            self.appendleft(t)
    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.construct(self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(self.data_r)
        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,p[:k-1])
s_max=SWAG(0,max,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: Accepted

Solution code:
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=[self.unit]
        self.fold_l=[self.unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    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.construct(self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(self.data_r)
        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,p[:k-1])
s_max=SWAG(0,max,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: Accepted

Solution code:
class SWAG():
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=[self.unit]
        self.fold_l=[self.unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    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.construct(self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(self.data_r)
        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,p[:k-1])
s_max=SWAG(0,max,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: Accepted

Solution code:
class SWAG():
    __slots__=('unit','f','fold_r','fold_l','data_r','data_l')
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    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.__init__(self.unit,self.f,self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__init__(self.unit,self.f,self.data_r)
        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,p[:k-1])
s_max=SWAG(0,max,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: Accepted

Solution code:
class SWAG():
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        list(map(self.append,data[sep:]))
        list(map(self.appendleft,data[sep-1::-1]))
    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.__init__(self.unit,self.f,self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__init__(self.unit,self.f,self.data_r)
        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,p[:k-1])
s_max=SWAG(0,max,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: Accepted

Solution code:
class SWAG():
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        *_,=map(self.append,data[sep:])
        *_,=map(self.appendleft,data[sep-1::-1])
    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.__init__(self.unit,self.f,self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__init__(self.unit,self.f,self.data_r)
        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,p[:k-1])
s_max=SWAG(0,max,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: Accepted

Solution code:
class SWAG():
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    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.__init__(self.unit,self.f,self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__init__(self.unit,self.f,self.data_r)
        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,p[:k-1])
s_max=SWAG(0,max,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)