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: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
class SegTree:
    def __init__(self,size):
        self.N=size
        self.v=[-1]*(2*self.N-1)
        self.w=[10**6]*(2*self.N-1)
    def update(self,i,x):
        i+=self.N-1
        self.v[i]=x
        self.w[i]=x
        while i>0:
            i=(i-1)//2
            self.v[i]=max(self.v[i*2+1],self.v[i*2+2])
            self.w[i]=min(self.w[i*2+1],self.w[i*2+2])
    def max(self,a,b,i=0,l=0,r=1e9):
        if r==1e9:
            r=self.N
        if r<=a or b<=l:
            return -1
        if a<=l and r<=b:
            return self.v[i]
        return max(self.max(a,b,i*2+1,l,(l+r)//2),self.max(a,b,i*2+2,(l+r)//2,r))
    def min(self,a,b,i=0,l=0,r=1e9):
        if r==1e9:
            r=self.N
        if r<=a or b<=l:
            return 10**6
        if a<=l and r<=b:
            return self.w[i]
        return min(self.min(a,b,i*2+1,l,(l+r)//2),self.min(a,b,i*2+2,(l+r)//2,r))
s=SegTree(2**18)
x,n=0,0
for i,p in enumerate(P):
    s.update(i,p)
    if P[i-1]<P[i]:
        x+=1
        if K-1<=i and x==K-1:
            n+=1
            x-=1
    else:
        x=0
r=1
n=max(0,n-1)
for i in range(N-K):
    m,M=s.min(i+1,K+i),s.max(i+1,K+i)
    if not (P[i]<m and M<P[K+i]):
        r+=1
print(max(1,r-n))

Submission status: Time Limit Exceeded

Solution code:
import copy

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

for i in range(N-K+1):
  target = copy.deepcopy(P)

  p = P[i:i+K]
  p.sort()
  
  target[i:i+K] = p
  if not(target in kk):
  	kk.append(target)
  
print(len(kk))

Submission status: Time Limit Exceeded

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

p_before = 200001
up = 0

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == min(p_list[(i-k):i]):
            if p_list[i] != max(p_list[(i-k+1):(i+1)]):
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
s = set()
for i in range(n-k+1):
    sub=sorted(p[i:i+k])
    a=[]
    a.extend(p[:i])
    a.extend(sub)
    a.extend(p[i + k:])
    s.add(''.join(str(a)))
print(len(s))

Submission status: Time Limit Exceeded

Solution code:

from sys import stdin
import heapq
import copy

N, K = [int(x) for x in stdin.readline().rstrip().split()]
Ps = [int(x) for x in stdin.readline().rstrip().split()]

lib =[]
count = N-K+1
ans = 0

for i in range(count):
    test = Ps[i:i+K]
    h = []
    for value in test:
        heapq.heappush(h, value)
    testq = [heapq.heappop(h) for i in range(len(h))]
    com = copy.copy(Ps)
    com[i:i+K] = testq
    if i == 0:
        lib.append(com)
        ans += 1
    else:
        if com in lib:
            None
        else:
            ans += 1
            lib.append(com)
print(ans)

Submission status: Time Limit Exceeded

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

A = []
for i in range(N - K + 1):
  Q = P[i:i+K] # P[i], P[i+1], ... , P[i+K-1]
  Q.sort()
  a = P[:i] + Q + P[i+K:]
  aa = map(str, a)
  aaa = "".join(aa)
  A.append(aaa)

A_set = list(set(A))
ans = len(A_set)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int, input().split())
p = np.array(list(map(int, input().split())))
res = 1


for i in range(0, n - k):
    if i == 0:
        partp = p[0:k]
        sortpartp = np.sort(partp)
        if not ((partp == sortpartp).all()):
            res += 1
    else:
        rightp = p[i + k - 1]
        leftp = p[i - 1]
        partp = np.append(partp, rightp)
        partp = np.delete(partp, 0)
        sortpartp = np.sort(partp)
        if ((partp == sortpartp).all()) or (
            np.min(partp) > leftp and np.max(partp) == rightp
        ):
            pass
        else:
            res += 1


print(res)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
P = list(map(int, input().split()))
P2 = P[:]
arr= []
ans = 0
for i in range(N-K+1):
    P[i:i+K] = sorted(P[i:i+K])
    #print(P)
    if i ==0:
            arr.append(P)
            ans +=1
    for j in range(len(arr)):
        if arr[j]==P:
            break
        if j == len(arr)-1:
            arr.append(P)
            ans +=1
    P = P2[:]


#print(arr)
print(ans)

Submission status: Time Limit Exceeded

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

count = dict()

for i in range(N - K + 1):
  new_P = P[:i] + sorted(P[i:i+K]) + P[i+K:]
  key = ''.join(map(str, new_P))
  count[key] = count.get(key, 0) + 1

print(len(count))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

p_before = 200001
up = 0

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == min(p_list[(i-k):i]):
            if p_list[i] != max(p_list[(i-k+1):(i+1)]):
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)

Submission status: Time Limit Exceeded

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

c = 0
for i in range(n-k):
  if p[i] == min(p[i:i+k+1]) and p[i+k] == max(p[i:i+k+1]) and p[i:i+k+1] != sorted(p[i:i+k+1]):
    c += 1

d = 0
for i in range(n-k+1):
  if p[i:i+k] == sorted(p[i:i+k]):
    d += 1
    
print(n-k+1-c-max(d-1,0))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
PP = set()
for i in range(N-K+1):
    s = sorted(([P[_] for _ in range(i,i+K)]))
    ss = [P[_] for _ in range(i+K,N)]
    ssss = [P[_] for _ in range(i)]
    sss = tuple(ssss+s+ss)
    if tuple(sss) not in PP:
        PP.add(sss)
print(len(PP))

Submission status: Time Limit Exceeded

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

s = [1]*N
r = 0
for l in range(N):
    r = max(l,r)
    while r < N-1:
        if P[r]<P[r+1]:
            r += 1
        else:
            break
    s[l] = r-l+1
    
q = deque([N]+P[:K-1])

ans = 0

for i in range(N-K+1):
    q.append(P[i+K-1])
    if min(q)!=P[i-1] or max(q)!=P[i+K-1]:
        if s[i]<K:
            ans += 1
    q.popleft()

if max(s) >= K:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# input parameter N, K
n, k = map(int, input().split())

# input parameter List
p_list = input().split()

# checked list
checked_list = []

# check operation
for start_index in range(n - k + 1):
    # temporary list
    temp_list = []
    
    # head list
    temp_list.extend(p_list[0:start_index])
    
    slice_list = p_list[start_index:start_index + k]
    
    # body list
    temp_list.extend(sorted(slice_list))
    
    # trail list
    temp_list.extend(p_list[start_index + k:])
    
    is_exist = False
    for checked_list_item in checked_list:
        if (checked_list_item == temp_list):
            is_exist = True
            break
    
    if not is_exist:
        checked_list.append(temp_list)

# print result
print(len(checked_list))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
p = [int(i) for i in input().split()]
ans = []
same = []
for i in range(n-k+1):
  temp = p[i:i+k]
  te = sorted(temp)
  if i>0 and i<n-k:
      seg = p[:i]+te+p[i+k:]
  elif i==0:
      seg = te + p[i+k:]
  else:
    seg = p[:i]+te
  if ans.count(seg)==0:
    ans.append(seg)
  if te==temp and len(same)>0:
    ans.remove(seg)
    same.append(i)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

lst = []

for i in range(N-K+1):
    l = P[:i] + sorted(P[i:i+K]) + P[i+K:]    
    if l in lst:
        continue
    lst.append(l)

print(len(lst))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res



class UnionFind:
    def __init__(self, size):
        self.UF = list(range(size))
        self.SIZE = [1] * size  # 0-indexed

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

    def unite(self, x, y):
        is_same = self.is_same
        find = self.find
        SIZE = self.SIZE
        UF = self.UF
        if not is_same(x, y):
            X, Y = find(x), find(y)
            SX, SY = SIZE[X], SIZE[Y]
            if SX > SY:
                m = UF[X] = Y
            else:
                m = UF[Y] = X
            SIZE[m] = SX + SY
            SIZE[X + Y - m] = 0

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

    def scan_uf(self):
        find = self.find
        length = len(self.UF)
        for i in range(length):
            find(i)

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


N, K = [int(_) for _ in input().split()]
P = [int(_) for _ in input().split()]
STmax = SegmentTree(array=P, f=max, ti=-float('inf'))
STmin = SegmentTree(array=P, f=min, ti=float('inf'))
UF = UnionFind(N - K + 1)
for i in range(N - K):
    if P[i] == STmin.query(i, i + K) and P[i + K] == STmax.query(
            i + 1, i + K + 1):
        UF.unite(i, i + 1)
inc = 0
incK = []
for i in range(N - 2, -1, -1):
    if P[i] <= P[i + 1]:
        inc += 1
        if inc >= K - 1:
            incK += [i]
    else:
        inc = 0
for i in incK:
    UF.unite(incK[0], i)
UF.scan_uf()
print(len(set(UF.UF)))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
PP = set()
for i in range(N-K+1):
    s = sorted(([P[_] for _ in range(i,i+K)]))
    ss = [P[_] for _ in range(i+K,N)]
    ssss = [P[_] for _ in range(i)]
    sss = tuple(ssss+s+ss)
    if tuple(sss) not in PP:
        PP.add(sss)
print(len(PP))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
p = (n - k) + 1
c = []
for i in range(p):
  b = a.copy()
  o = sorted(set(a[i: i+k]))
  b[i: i+k] = o
  c.append(b)
d = set(list(map(tuple, c)))
print(len(d))

Submission status: Time Limit Exceeded

Solution code:
import copy
n,k = map(int,input().split())
p_li = list(map(int,input().split()))

ans_li = []
for i in range(n):
    buf = []
    buf = copy.deepcopy(p_li)
    #print("buf = ", buf)
    sort_p = buf[i : i + k]
    #print("sort_p = ", sort_p)
    sort_p.sort()
    buf[i:i + k] = sort_p
    #print(buf[i:i + k])
    #print(buf)
    #print("p_li = ", p_li)
    # buf_s = ""
    """
    for j in range(n):
        buf_s = buf_s + str(buf[j]) + ","
    ans_li.append(buf_s)
    """
    ans_li.append(buf)
    if i + k == n:
        break
print(len(list(map(list, set(map(tuple, ans_li))))))
#print(len(list(set(ans_li))))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

pset = set()

for i in range(N-K+1):
    l = P[:i] + sorted(P[i:i+K]) + P[i+K:]
    l = "".join([str(t) for t in l])
    pset.add(l)

print(len(pset))

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq
N, K = map(int, input().split())
P = list(map(int, input().split()))
diff = [P[i+1] - P[i] for i in range(N-1)]
table = collections.defaultdict(int)

if P == sorted(P):
    print(1)
    exit(0)


else:
    for i in range(N-K + 1):
        tmp = [0] * N
        tmp[:i] = P[:i]
        tmp2 = P[i:i+K]
        heapq.heapify(tmp2)
        for j in range(K):
            tmp[i+j] = (heapq.heappop(tmp2))
        tmp[i+K:] = P[i+K:]
        table["".join(map(str, tmp))] += 1

print(len(table.keys()))

Submission status: Time Limit Exceeded

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

for i in range(N - K + 1):
  target = P[i:i+K]
  target.sort()
  new_list = P[:i] + target + P[i+K:]
  res_set.add(''.join(new_list))

print(len(res_set))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
s=[]
for i in range(n-k+1):
    s.append(p[:i]+sorted(p[i:i+k])+p[i+k:])
s.sort()
#print(s)
kosuu=1
for i in range(len(s)-1):
    if s[i]!=s[i+1]:
        kosuu+=1
print(kosuu)

Submission status: Time Limit Exceeded

Solution code:
import copy
n,k = map(int,input().split())
p_li = list(map(int,input().split()))

ans_li = []
for i in range(n):
    buf = []
    buf = copy.deepcopy(p_li)
    #print("buf = ", buf)
    sort_p = buf[i : i + k]
    #print("sort_p = ", sort_p)
    sort_p.sort()
    buf[i:i + k] = sort_p
    #print(buf[i:i + k])
    #print(buf)
    #print("p_li = ", p_li)
    buf_s = ""
    for j in range(n):
        buf_s = buf_s + str(buf[j]) + ","
    ans_li.append(buf_s)
    if i + k == n:
        break
    
print(len(list(set(ans_li))))

Submission status: Time Limit Exceeded

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

lst = []

for i in range(N-K+1):
    l = P[:i] + sorted(P[i:i+K]) + P[i+K:]
    l = "".join([str(t) for t in l])
    lst.append(l)

set(lst)
print(len(set(lst)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
def f(li):
    s = []
    return len([x for x in li if x not in s and not s.append(x)])

N, K = [int(x) for x in input().split(" ")]
nums = [int(x) for x in input().split(" ")]
samples = []
 
for i in range(N - K + 1):
    sli = nums[i:i + K]
    sli.sort()
    sli2 = nums[:i] + sli + nums[i + K:]
    samples.append(sli2)
 
print(f(samples))

Submission status: Time Limit Exceeded

Solution code:
import copy

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

h = {}
for i in range(0, N-K+1):
  p = copy.copy(P)
  sub = p[i:i+K]
  sub.sort()
  p[i:i+K] = sub
  h["".join(map(str, p))] = 1

print(len(h))

Submission status: Time Limit Exceeded

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

G = set()
for i in range(N-K+1):
  S = P[i:i+K]
  S.sort()
  #print(S)
  if i == 0:
    PS = S+P[i+K:N]
  elif i == N-K:
    PS = P[0:i]+S
  else:
    PS = P[0:i]+S+P[i+K:N]
  G.add(tuple(PS))
#print(G)
print(len(G))

Submission status: Time Limit Exceeded

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

s = set()

for i in range(N-K+1):
    p = P[:i] + sorted(P[i:i+K]) + P[i+K:]
    s.add(tuple(p))
print(len(s))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K = map(int,input().split())

a = list(input().split())
p = np.zeros(N)
for i in range(N):
    p[i] = a[i]
count = 1
temp1 = p
temp2 = p
temp2[:K].sort()

for i in range(1,N - K + 1):
    temp1 = temp2
    temp2 = p.copy()
    temp2[i:i+K].sort()

    if (temp1[i - 1:i+K] != temp2[i - 1:i + K]).any():
        count +=1
    #print(temp1,temp2)


print(count)

Submission status: Time Limit Exceeded

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

ans=[]
for i in range(n-k+1):
  sorted_P=P[:i]+sorted(P[i:i+k])+P[i+k:]
  ans.append(tuple(sorted_P))
print(len(set(ans)))

Submission status: Time Limit Exceeded

Solution code:
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

import copy

N, K = input().split()
N = int(N)
K = int(K)

p_list = input().split()
start_p_list = [int(p) for p in p_list]

new_list = []
for i in range(len(p_list) - K + 1):
  p_list = copy.copy(start_p_list)
  ex_list = p_list[i:i+K]
  ex_list.sort()
  p_list[i:i + K] = ex_list
  p_list_c = copy.copy(p_list)
  new_list.append(p_list_c)

print(len(get_unique_list(new_list)))

Submission status: Time Limit Exceeded

Solution code:
n, k = tuple(map(int, input().split()))
P = list(map(int, input().split()))
result = []
for i in range(n-k):
    result.append(str(P[:i]) + str(sorted(P[i:i+k+1])) + str(P[i+k+2:]))
if result:
    result_length = len(set(result))
else:
    result_length = 1
print(result_length)

Submission status: Time Limit Exceeded

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

sorted_p = []

for i in range(n-k+1):
  sorted_p.append(p[:0+i] + sorted(p[0+i:k+i]) + p[k+i:])

seen = []
[x for x in sorted_p if x not in seen and not seen.append(x)]

print(len(seen))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


def main():
    N, K = map(int, input().split())

    nums = list(map(int, input().split()))

    ans = set()

    for i in range(len(nums) - K + 1):
        t = deepcopy(nums)
        t[i:i+K] = sorted(t[i:i+K])
        ans.add(''.join(map(str, t)))

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import copy

N, K = [int(x) for x in input().split(" ")]
nums = [int(x) for x in input().split(" ")]
samples = []

for i in range(N - K + 1):
    sli = copy.copy(nums[i:i + K])
    sli.sort()
    sli2 = copy.copy(nums[:i] + sli + nums[i + K:])
    if sli2 in samples:
        continue
    samples.append(sli2)

print(len(samples))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

# input = sys.stdin.readline


def main():
    N, K = map(int, input().split())

    nums = list(map(int, input().split()))

    ans = set()

    for i in range(len(nums) - K + 1):
        t = deepcopy(nums)
        t[i:i+K] = sorted(t[i:i+K])
        ans.add(''.join(map(str, t)))

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
p = [int(i) for i in input().split()]
ans = []
for i in range(n-k+1):
  temp = p[i:i+k]
  temp.sort()
  if i>0 and i<n-k:
    seg = p[:i]+temp+p[i+k:]
  elif i==0:
    seg = temp + p[i+k:]
  else:
    seg = p[:i]+temp
  if ans.count(seg)==0:
    ans.append(seg)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
a=set()
N,K=map(int,input().split())
*P,=map(int,input().split())
for i in range(N-K+1):
    a.add(tuple(P[:i]+sorted(P[i:i+K])+P[i+K:]))
print(len(a))

Submission status: Time Limit Exceeded

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

ans=[]
for i in range(n-k+1):
  sorted_P=P[:i]+sorted(P[i:i+k])+P[i+k:]
  if sorted_P not in ans:
    ans.append(sorted_P)
print(len(ans))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
from heapq import heappop,heappush,heapify


import heapq
class pqheap:
  def __init__(self,key=None):
    self.p = list()
    self.q = list()

  def insert(self,x):
    heapq.heappush(self.p, x)
    return

  def erase(self,x):
    heapq.heappush(self.q, x)
    return

  def minimum(self):
    while self.q and self.p[0] == self.q[0]:
      heapq.heappop(self.p)
      heapq.heappop(self.q)
    return self.p[0] if len(self.p)>0 else None
minheap=pqheap()
maxheap=pqheap()
for i in range(k):
  minheap.insert(p[i])
  maxheap.insert(-p[i])
ans=1
premin=minheap.minimum()
premax=-maxheap.minimum()

for i in range(k,n):
  ins=p[i]
  era=p[i-k]
  minheap.erase(era)
  maxheap.erase(-era)
  minheap.insert(ins)
  maxheap.insert(-ins)
  if premin==era and ins==-maxheap.minimum():
    pass
  else:
    ans+=1
  premax=-maxheap.minimum()
  premin=minheap.minimum()
ans0=0
now=1
pre=p[0]
for x in p[1:]:
  if x>pre:
    now+=1
  else:
    now=1
  if now==k:
    ans0+=1
  pre=x


print(ans-max(0,ans0-1))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

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

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

up_check_acc = list(accumulate(up_check))
for i in range(N-K+1):
	if up_check_acc[i+K-1]-up_check_acc[i] == K-1:
		check[i] = 1

q1 = sorted((P[:K]))
q2 = [N]
q3 = sorted([-x for x in P[:K]])
q4 = [N]

ans = N-K+1
for i, p in enumerate(P[K:]):
	heappush(q1, p)
	heappush(q3, -p)
	while q1[0] == q2[0]:
		heappop(q1)
		heappop(q2)

	while q3[0] == q4[0]:
		heappop(q3)
		heappop(q4)

	if q1[0] == P[i] and q3[0] == -p and check[i]*check[i+1] == 0:
		ans -= 1

	heappush(q2, P[i])
	heappush(q4, -P[i])

ans -= max(0, sum(check)-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
Ps = list(mapint())

def segfunc(x, y):
    return min(x, y)

def segfunc_2(x, y):
    return max(x, y)

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

if N==K:
    print(1)
    exit()
seg_min = SegTree(Ps, segfunc, 10**18)
seg_max = SegTree(Ps, segfunc_2, -1)

str_set = set()
cnt = 1
old = 10**18
is_increase = [0]*N
for i in range(N):
    p = Ps[i]
    if p>old:
        cnt += 1
        is_increase[i] = cnt
    else:
        cnt = 1
        is_increase[i] = cnt
    old = p

original = 0
ans = N-K+1
for i in range(N-K):
    mini = Ps[i]
    maxi = Ps[i+K]
    if is_increase[i+K-1]>=K:
        original = 1
        ans -= 1
    elif (seg_min.query(i, i+K+1)==mini and seg_max.query(i, i+K+1)==maxi):
        ans -= 1
if is_increase[-1]>=K:
    original = 1
    ans -= 1
print(ans+original)

Submission status: Accepted

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

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

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

    N0 = 2 ** (N.bit_length())
    st1 = [0] * (2 * N0)
    st2 = [0] * (2 * N0)

    i = N0-1
    for x in P:
        st1[i] = st2[i] = x
        i += 1


    for i in range(N0-2,-1,-1):
        st1[i] = max(st1[i*2+1],st1[i*2+2])
        st2[i] = min(st2[i*2+1],st2[i*2+2])

    def query_max(l, r):
        L = l + N0;
        R = r + N0
        ret = 0
        while L < R:
            if L % 2:
                ret = max(ret, st1[L - 1])
                L += 1
            if R % 2:
                R -= 1
                ret = max(ret, st1[R - 1])
            L //= 2;
            R //= 2
        return ret


    def query_min(l, r):
        L = l + N0;
        R = r + N0
        ret = N + 1  # max value
        while L < R:
            if L % 2:
                ret = min(ret, st2[L - 1])
                L += 1
            if R % 2:
                R -= 1
                ret = min(ret, st2[R - 1])
            L //= 2;
            R //= 2
        return ret


    ans = 0
    cnt = 0
    flg = 0
    bp = N
    for i in range(N):
        if P[i] > bp:
            cnt += 1
        else:
            cnt = 0
        bp = P[i]

        if i < K - 1: continue

        if cnt >= K-1:
            flg = 1
        elif i >= K and query_min(i-K,i) == P[i-K] and query_max(i-K+1,i+1) == P[i]:
            pass
        else:
            ans += 1

    print(ans+flg)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    S = [] # min
    T = [] # max
    D = deque()
    C = 0 # swap count

    for k in range(K):
        a = A[k]
        heapq.heappush(S, (a, k))
        heapq.heappush(T, (-a, k))
        if k > 0:
            c = 1 if A[k - 1] > A[k] else 0
            D.append(c)
            C += c

    r = 0
    F = True if C == 0 else False
    res = 0 if F else 1

    # print(f"A: {A[0:K]}")
    # print(f"S: {S[0][0]}, T: {-T[0][0]}, C: {C}")
    # print(f"res: {res}, F: {F}")
    for i in range(N - K):
        # update swap
        C -= D.popleft()
        c = 1 if A[K + i - 1] > A[K + i] else 0
        D.append(c)
        C += c

        out_a = A[i]
        in_a = A[K + i]
        
        # update T
        heapq.heappush(T, (-in_a, K + i))
        while T[0][1] <= i:
            heapq.heappop(T)

        if C == 0:
            F = True
        else:
            if not (T[0][0] == -in_a and S[0][0] == out_a):
                res += 1

        # print(f"in: {in_a}, out: {out_a}")
        # update S
        heapq.heappush(S, (in_a, K + i))
        while S[0][1] <= i:
            heapq.heappop(S)
        # print(f"S: {S[0][0]}, T: {-T[0][0]}, C: {C}")
        # if K + i + 1 < N:
       #      print(f"A: {A[i + 1:i+K+1]}")
        # print(f"res: {res}, F: {F}")
    if F:
        res += 1
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def segfunc_min(x,y):return min(x,y)
def segfunc_max(x,y):return max(x,y)
ide_ele_min=10**18
ide_ele_max=0
class segtree():
  def __init__(self,init_val,segfunc,ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,k=map(int,input().split())
*p,=map(int,input().split())
q=[1]*n
ans=n-k+1
cnt=1
c=0
for i in range(n-1):
  if p[i+1]>p[i]:cnt+=1
  else:cnt=1
  c+=cnt>=k
  if cnt>k:q[i-k+1]=0
if c>1:ans-=c-1
stn=segtree(p,segfunc_min,ide_ele_min)
stx=segtree(p,segfunc_max,ide_ele_max)
for i in range(n-k):
  if stn.query(i,i+k)==p[i] and stx.query(i+1,i+k+1)==p[i+k] and q[i]:ans-=1
print(ans)