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:
#!/usr/bin/env python3
#AGC38 B
#スライド最小値

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
p = LI()
ans = 0
que = deque()
que.append(0)
minlst = []
for i in range(1,n):
    if p[que[-1]] < p[i]:
        que.append(i)
    else:
        while que:
            if p[que[-1]] < p[i]:
                que.append(i)
                break
            else:
                que.pop()
        else:
            que.append(i)
    if i >= k:
        minlst.append(p[que[0]])
        if que[0] == i - k:
            que.popleft()
minlst.append(p[que[0]])
que = deque()
que.append(0)
maxlst = []
for i in range(1,n):
    if p[que[-1]] > p[i]:
        que.append(i)
    else:
        while que:
            if p[que[-1]] > p[i]:
                que.append(i)
                break
            else:
                que.pop()
        else:
            que.append(i)
    if i >= k-1:
        maxlst.append(p[que[0]])
        if que[0] == i - k:
            que.popleft()

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]
def union(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

lst = []
cnt = 1
tmp = p[0]
for i in range(1,n):
    if tmp < p[i]:
        cnt += 1
    else:
        if cnt >= k:
            lst.append(i-k)
        cnt = 1
    tmp = p[i]
if cnt >= k:
    lst.append(i-cnt+1)
par = [i for i in range(n)]
rank = [0]*n
if len(lst) > 1:
    for i in lst:
        for j in lst[::-1]:
            union(i,j)
for i in range(n-k):
    if p[i] == minlst[i] and p[i+k] == maxlst[i+1]:
        union(i,i+1)
s = set()
for i in range(n-k+1):
    s.add(root(i))
print(len(s))

Submission status: Accepted

Solution code:
from collections import deque

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

maxQ = deque([])
minQ = deque([])

for i in range(K):
    while maxQ:
        if P[maxQ[-1]] <= P[i]:
            maxQ.pop()
        else:
            break
    maxQ.append(i)
    if maxQ[0] == i - K:
        maxQ.popleft()

    while minQ:
        if P[minQ[-1]] >= P[i]:
            minQ.pop()
        else:
            break
    minQ.append(i)
    if minQ[0] == i - K:
        minQ.popleft()

ans = 1
hasSame = False
seq = 1
for i in range(1, K):
    if P[i - 1] < P[i]:
        seq += 1
    else:
        seq = 1
if seq >= K:
    hasSame = True

for left in range(N - K):
    right = left + K

    if P[right - 1] < P[right]:
        seq += 1
    else:
        seq = 1

    while maxQ:
        if P[maxQ[-1]] <= P[right]:
            maxQ.pop()
        else:
            break
    maxQ.append(right)
    if maxQ[0] == right - K:
        maxQ.popleft()

    if left == minQ[0] and right == maxQ[0]:
        pass
    else:
        if seq < K:
            ans += 1
        else:
            if not hasSame:
                hasSame = True
                ans += 1

    while minQ:
        if P[minQ[-1]] >= P[right]:
            minQ.pop()
        else:
            break
    minQ.append(right)
    if minQ[0] == right - K:
        minQ.popleft()

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import itertools
# K = 3
# a = [1,3,5,4,2]
# N = len(a)

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

deq = deque()
min_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] >= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    min_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(min_val)

deq = deque()
max_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] <= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    max_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(max_val)

incr = [1 if x<y else 0 for x,y in zip(p, p[1:])]
incr_cum = [0] + list(itertools.accumulate(incr))
is_stable = [y-x==K-1 for x,y in zip(incr_cum,incr_cum[K-1:])]

cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  range_min = min_val[i]
  range_max = max_val[i]
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if is_stable[i]:
    sortMatchCnt += 1
    sortMatchFlg = True

  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  # preR = r
  prerange_min = range_min
  # prerange_max = range_max
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
xs = list(map(int, input().split()))
from collections import deque
def slide_max(k, l):
    rs, rrs = [], set()
    dq = deque()
    for i, x in enumerate(l):
        while True:
            if not len(dq):
                dq.append(i)
                break
            lxi = dq[-1]
            if x < l[lxi]:
                dq.append(i)
                break
            dq.pop()
        if i+1 < k:
            continue
        sxi = dq[0]
        rs.append(l[sxi])
        if sxi == (i + 1 - k):
            dq.popleft()
    return rs

def slide_min(k, l):
    rs = []
    rrs = set()
    dq = deque()
    for i, x in enumerate(l):
        while True:
            if not len(dq):
                dq.append(i)
                break
            lxi = dq[-1]
            if x > l[lxi]:
                dq.append(i)
                break
            dq.pop()
        if i+1 < k:
            continue
        if len(dq) == k:
            rrs.add(i+1-k)
        sxi = dq[0]
        rs.append(l[sxi])
        if sxi == (i + 1 - k):
            dq.popleft()
    return rs, rrs

maxs, (mins, ns) = slide_max(k, xs), slide_min(k, xs)
r = 1
for i, (s, x) in enumerate(zip(xs, xs[k:])):
    if (x != maxs[i+1] or s != mins[i]) and (i+1 not in ns): 
        r+=1
if (0 not in ns) and (len(ns) > 0):
    r += 1
print(r)

Submission status: Accepted

Solution code:
from collections import deque
def slidemax(X, k):
    q = deque([])
    ret = []
    for i in range(len(X)):
        while q and q[-1][1] <= X[i]:
            q.pop()
        deque.append(q, (i+k, X[i]))
        if q[0][0] == i:
            deque.popleft(q)
        if i >= k-1:
            ret.append(q[0][1])
    return ret

def slidemin(X, k):
    q = deque([])
    ret = []
    for i in range(len(X)):
        while q and q[-1][1] >= X[i]:
            q.pop()
        deque.append(q, (i+k, X[i]))
        if q[0][0] == i:
            deque.popleft(q)
        if i >= k-1:
            ret.append(q[0][1])
    return ret

N, K = map(int, input().split())
A = [int(a) for a in input().split()]

a = 0
l = -1
cnt = 0
for i in range(1, N):
    if A[i-1] > A[i]: a = i
    if i >= K-1 and a <= i - K + 1:
        if i - l > 1: cnt += 1
        l = i

MA = slidemax(A, K)
MI = slidemin(A, K)
ans = 1 - max(cnt-1, 0)
l = -1
for i in range(K, N):
    if MI[i-K] != A[i-K] or MA[i-K+1] != A[i]:
        ans += 1

print(ans)

Submission status: Accepted

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

from collections import deque
def slide_max(k, l):
    rs = []
    dq = deque()
    for i, x in enumerate(l):
        while True:
            if not len(dq):
                dq.append(i)
                break
            lxi = dq[-1]
            if x < l[lxi]:
                dq.append(i)
                break
            dq.pop()
        if i+1 < k:
            continue
        sxi = dq[0]
        rs.append(l[sxi])
        if sxi == (i + 1 - k):
            dq.popleft()
    return rs

def slide_min(k, l):
    rs = []
    dq = deque()
    for i, x in enumerate(l):
        while True:
            if not len(dq):
                dq.append(i)
                break
            lxi = dq[-1]
            if x > l[lxi]:
                dq.append(i)
                break
            dq.pop()
        if i+1 < k:
            continue
        sxi = dq[0]
        rs.append(l[sxi])
        if sxi == (i + 1 - k):
            dq.popleft()
    return rs

maxs, mins = slide_max(k, xs), slide_min(k, xs)
aa, bb = xs[:k], xs[k:]

b, nb, bx = aa[0], aa[1], aa[-1]
ba = None
c = 1
for a in aa:
    if ba == None:
        ba = a
        continue
    if a > ba:
        c += 1
    else:
        c = 1
    ba = a

rok = False
if c == k:
    rok = True

r = 1
bs = xs[0]
for i, (s, x) in enumerate(zip(xs[1:], bb)):

    if x > bx:
        c = min(c+1, k)
    else:
        c = 1
    bx = x

    if c == k:
        if not rok:
            r += 1
        rok = True
        continue

    if x != maxs[i+1]: 
        r+=1
    elif bs != mins[i]:
        r+=1
    bs = s

print(r)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
INF = 10**10
MOD = 10**9+7

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0] * n
        self.size = [1] * n

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

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

def slide_min(a, k):
    n = len(a)
    b = [None] * (n-k+1)
    deq = deque()
    for i in range(n):
        while len(deq) > 0 and a[i] <= a[deq[-1]]:
            deq.pop()
        deq.append(i)
        if i-k+1 >= 0:
            b[i-k+1] = a[deq[0]]
            if deq[0] == i-k+1:
                deq.popleft()
    return b

def slide_max(a, k):
    n = len(a)
    b = [None] * (n-k+1)
    deq = deque()
    for i in range(n):
        while len(deq) > 0 and a[i] >= a[deq[-1]]:
            deq.pop()
        deq.append(i)
        if i-k+1 >= 0:
            b[i-k+1] = a[deq[0]]
            if deq[0] == i-k+1:
                deq.popleft()
    return b

N, K = map(int, input().split())
P = [int(x) for x in input().split()]
uf1 = UnionFind(N)
for i in range(N-1):
    if P[i] < P[i+1]:
        uf1.unite(i, i+1)
vs = []
for i in range(N-K+1):
    if uf1.same(i, i+K-1):
        vs.append(i)
uf2 = UnionFind(N)
if len(vs) > 1:
    for v1, v2 in zip(vs, vs[1:]):
        uf2.unite(v1, v2)
m, M = slide_min(P, K), slide_max(P, K)
for i in range(N-K):
    if P[i] == m[i] and P[i+K] == M[i+1]:
        uf2.unite(i, i+1)
s = set()
for i in range(N-K+1):
    s.add(uf2.find(i))
print(len(s))