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:
import bisect
N,K = map(int,input().split(' '))
P = list(map(int,input().split(' ')))

'''
import random
N = 2000
K = 100
P = random.sample(list(range(N)),N)
#P = list(range(N))[::-1]
#print("P",P)
'''

def simple():
	s = set({})
	for i in range(N-K+1):
		Q = tuple(P[:i]+sorted(P[i:i+K])+P[i+K:])
		s.add(Q)
	return len(s)

ans = 0
mi = -1 
sp = sorted(P[:K])
if sp != P[:K]:
	ans += 1
else:
	ans += 1
	mi += 1

pre_pos = 0
for i in range(1,N-K+1):
	f = False
	if sp[0] != P[i-1]:
		f = True
	if sp[-1] > P[i+K-1]:
		f = True

	#sp.remove(P[i-1])
	del sp[bisect.bisect_left(sp,P[i-1])]
	bisect.insort(sp,P[i+K-1])
	#pos = bisect.bisect_left(sp,P[i+K-1])
	#sp.insert(pos,P[i+K-1])

	if f and sp == P[i:K+i]:
		mi += 1
	ans += int(f)
	#print(f,sp)
	#print(P[:i]+sp+P[K+i:])

ans -= max(0,mi)
#print(mi)
#print("ans",simple())
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
num,div= input().split()
num = int(num)
div = int(div)
ar = np.array(list(map(int, input().split())))
box = []

for i in range(0,num-div+1):
  if i==0:
    result = np.hstack((np.sort(ar[:div]),ar[div:]))
  elif i<num-div:
    result = np.hstack((ar[:i],np.sort(ar[i:i+div]),ar[i+div:]))
  else:
    result = np.hstack((ar[:div],np.sort(ar[div:])))
  box.append(result)
print(len(np.unique([str(x) for x in box])))

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, K = map(int, input().split())
p = list(map(int, input().split()))
cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  range_min = min(p[i:i + K])
  range_max = max(p[i:i + K])
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if range_min == l and range_max == r:
    sortMatchFlg = p[i:i + K] == sorted(p[i:i + K])
    if sortMatchFlg:
      sortMatchCnt += 1                      

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

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

ans = set()

for i in range(n - k + 1):
    cpy = deepcopy(p)
    cpy[i:i+k] = sorted(cpy[i:i+k])
    ans.add(tuple(cpy))

print(len(ans))

Submission status: Time Limit Exceeded

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

A = set()
for i in range(0, N-K+1):
  X = P.copy()
  X[i:i+K] = sorted(X[i:i+K])
  A.add(tuple(X))
  
print(len(A))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree():
    def __init__(self, values, merge_func=min, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        self.merge = merge_func
        while self.size < n:
            self.size *= 2
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [self.default] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.default
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return self.merge(left, right)

    # query segmentation value of [a, b)
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    seq = 1
    for i in range(K-1):
        if P[i] < P[i+1]:
            seq += 1
        else:
            seq = 1
    has_orig = seq == K
    rmq = SegmentTree(P)
    rMq = SegmentTree(P, merge_func=max, default=-1)
    ans = 1
    for i in range(N-K):
        if P[i+K-1] < P[i+K]:
            seq += 1
        else:
            seq = 1
        if seq >= K:
            if not has_orig:
                has_orig = True
                ans += 1
            continue
        if P[i] != rmq.query(i, i+K+1) or P[i+K] != rMq.query(i, i+K+1):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

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)]
  
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()
  b[i: i+k] = sorted(set(b[i: i+k]))
  c.append(b)
  
d = get_unique_list(c)
#d = set(list(map(tuple, c)))
print(len(d))

Submission status: Time Limit Exceeded

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

s=0
e=k
w_d = set()

if n==k:
  print(1)
else:
  while True:
    left=''
    right=''
    tmp = l[s:e]
    tmp.sort()
    tmp = ''.join(list(map(str, tmp)))
    if s!=0:
      try:
        left = ''.join(list(map(str, l[:s])))
      except:
        left = str(l[:s])
    if e!=n:
      try:
        right = ''.join(list(map(str, l[e:])))
      except:
        right = str(l[e:])
    word = left+tmp+right
    w_d.add(word)
    if e==n:
      break
    s += 1
    e += 1
  print(len(w_d))

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:
num, sortNum = [int(i) for i in input().split()]
targetList = [int(i) for i in input().split()]
answerList = []
for idx in range(num - sortNum + 1):
    tmpList = targetList[:idx] + sorted(targetList[idx:idx+sortNum]) + targetList[idx+sortNum:]
    tmpStr = ','.join([str(i) for i in tmpList])
    if (tmpStr in answerList) == False:
        answerList.append(tmpStr)
print(len(answerList))

Submission status: Time Limit Exceeded

Solution code:
def main():

    n,k=map(int,input().split())
    x=list(map(int,input().split()))
    
    min_list=[]
    max_list=[]
    
    segtree=[n+1]*524288
    
    for i in range(262143,262143+n):
        segtree[i]=x[i-262143]
    	
    for i in range(262142,-1,-1):
        segtree[i]=min(segtree[2*i+1],segtree[2*i+2])
    
    def search(i,j,now):
        for k in range(20):
            if 2**k-1<=now<2**(k+1)-1:
                break
        kubun=2**(k)
        now2=now-kubun+1
        width=262144//kubun
        left=width*now2
        right=width*(now2+1)-1
        if i<=left and right<=j:
            return segtree[now]
        elif j<left or right<i:
            return n+1
        else:
            return min(search(i,j,2*now+1),search(i,j,2*now+2))
    
    for i in range(n-k+2):
        min_list.append(search(i,i+k-2,0))
    
    segtree=[-1]*524288
    
    for i in range(262143,262143+n):
        segtree[i]=x[i-262143]
    	
    for i in range(262142,-1,-1):
        segtree[i]=max(segtree[2*i+1],segtree[2*i+2])
    
    def search(i,j,now):
        for k in range(20):
            if 2**k-1<=now<2**(k+1)-1:
                break
        kubun=2**(k)
        now2=now-kubun+1
        width=262144//kubun
        left=width*now2
        right=width*(now2+1)-1
        if i<=left and right<=j:
            return segtree[now]
        elif j<left or right<i:
            return -1
        else:
            return max(search(i,j,2*now+1),search(i,j,2*now+2))
    
    for i in range(n-k+2):
        max_list.append(search(i,i+k-2,0))
        
    cnt=0
    
    cnt=0
    flag=[True]*(n-k+1)
    first=False
    for i in range(n-1):
        if x[i]<x[i+1]:
            cnt+=1
        else:
            cnt=0
        if cnt>=k-1:
            if first==False:
                first=True
            else:
                flag[i-k+2]=False
    
    for i in range(1,n-k+1):
        if x[i-1]<min_list[i] and max_list[i]<x[i+k-1]:
            flag[i]=False
            
    print(sum(flag))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value, N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                self.node[i] = left_i
            else:
                self.node[i] = right_i

    def set_input(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                new_i = left_i
            else:
                new_i = right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def get_input(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def get_output(self, a=0, b=-1):
        return self.get_input(self.get_output_index(a,b))

    def get_output_index(self,
                         a=0, b=-1,
                         k=0, l=0, r=-1):
        if b < 0:
            b = self.N
        if r < 0:
            r = self.N
        if a <= l and r <= b:
            return self.node[k]
        elif r <= a or b <= l:
            return None
        else:
            left_i = self.get_output_index(a,b,2*k+1,l,(l+r)//2)
            right_i = self.get_output_index(a,b,2*k+2,(l+r)//2,r)
            left_v, right_v = self.get_input(left_i), self.get_input(right_i)
            if left_v is None and right_v is None:
                return None
            elif self.comp(left_v, right_v):
                return left_i
            else:
                return right_i

def get_sequence(arr):
    if len(arr) == 0:
        return [], []
    elements = []
    nums = []
    n = 1
    prev = arr[0]
    for c in arr[1:]:
        if c == prev:
            n += 1
        else:
            elements.append(prev)
            nums.append(n)
            prev = c
            n = 1
    elements.append(prev)
    nums.append(n)
    return elements, nums

N, K = inpl()
P = inpl()
minseg = SegmentTree(P)
maxseg = SegmentTree(P, reverse=True)

ans = 1
for i in range(N-K):
    if P[i] < minseg.get_output(i+1,i+K) and P[i+K] > maxseg.get_output(i+1,i+K):
        pass
    else:
        ans += 1

ordered = [ P[i] < P[i+1] for i in range(N-1)]
elements, nums = get_sequence(ordered)
nums = nums[(elements[0]+1)%2::2]

unchanged = len(list(filter(lambda x: x>=K-1, nums)))
if unchanged > 1:
    ans -= unchanged-1

print(ans)

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):
    _ = P[:i] + sorted(P[i : i+K]) + P[i+K : ]
    if _ not in S:
        S.append(_)
print(len(S))

Submission status: Time Limit Exceeded

Solution code:
def insert(target_list, target):
  for i in range(len(target_list) - 1):
    if target_list[i] < target and target < target_list[i+1]:
      target_list.insert(i+1, target)
      return
  target_list.append(target)

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

res_set = set()

target = []
for i in range(N - K + 1):
  if i == 0:
    target = P[i:i+K]
    target.sort()
  else:
    target.remove(P[i-1])
    insert(target, P[i+K-1])
  #print(target)
  new_list = P[:i] + target + P[i+K:]
  res_set.add(tuple(new_list))

#print(res_set)
print(len(res_set))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
# セグメント木(min, max)
N += 1
N0 = 2**(N-1).bit_length()
INF = float('inf')
minST = [INF]*(2*N0)
def update_min(k, x):
  k += N0-1
  minST[k] = x
  while k >= 0:
    k = (k - 1) // 2
    minST[k] = min(minST[2*k+1], minST[2*k+2])
def query_min(l, r):
  L = l + N0; R = r + N0
  s = INF
  while L < R:
    if R & 1:
      R -= 1
      s = min(s, minST[R-1])
    if L & 1:
      s = min(s, minST[L-1])
      L += 1
    L >>= 1; R >>= 1
  return s

MINF = float('-inf')
maxST = [MINF]*(2*N0)
def update_max(k, x):
  k += N0-1
  maxST[k] = x
  while k >= 0:
    k = (k - 1) // 2
    maxST[k] = max(maxST[2*k+1], maxST[2*k+2])

def query_max(l, r):
  L = l + N0; R = r + N0
  s = MINF
  while L < R:
    if R & 1:
      R -= 1
      s = max(s, maxST[R-1])
    if L & 1:
      s = max(s, maxST[L-1])
      L += 1
    L >>= 1; R >>= 1
  return s

Ps = list(map(int, input().split())) + [-1]
sorted_lens = []
tmp = 0
prev = -1
for i, p in enumerate(Ps):
  update_min(i, p)
  update_max(i, p)
  if prev > p:
    tmp = 0
  tmp += 1
  sorted_lens.append(tmp)
  prev = p

ans = N-K
flag = False
for i in range(N-K):
  smin = query_min(i, i+K+1)
  smax = query_max(i, i+K+1)
  if (smin == Ps[i] and smax == Ps[i+K]) or (flag and sorted_lens[i+K] >= K):
    ans -= 1
  if sorted_lens[i+K-1] == K:
    flag = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p = [str(i) for i in input().split()]

tempStr = ""
tempP = [""] * k
setP = set()
for i in range(n-k+1):
	for j in range(k):
		tempP[j] = p[i+j]
	tempP.sort()
	tempP2 = p[:i] + tempP[:] + p[i+k:]	
	setP.add("".join(tempP2))

print(len(setP))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
P = list(map(int,input().split()))
count = 0
first = 1
def isSorted(ls):
    for i in range(len(ls)-1):
        if ls[i]>=ls[i+1]:
            return 0
    return 1

for i in range(N-K+1):
    if isSorted(P[i:i+K])==1:
        if first == 1:
            count += 1
            first = 0
        continue
    elif (i!=0) and (P[i-1] < min(P[i:i+K-1])) and (P[i+K-1] > max(P[i:i+K-1])):
        continue
    else:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

count=n-k+1
first=0
pp=p[0:k]
pp_s=np.sort(pp)
for i in range(len(pp)):
    if pp_s[i]!=pp[i]:
        break
    if i==len(pp)-1:
        if first==0:
            first+=1
ma=np.max(pp)
mi=np.min(pp)

for i in range(1,n-k+1):
    pp=p[i:i+k]
    if pp[k-1]>ma:
        ma=pp[k-1]
    elif pp[k-1]<mi:
        mi=pp[k-1]
    if p[i-1]==mi:
        mi=np.min(pp)
    elif p[i-1]==ma:
        ma=np.max(pp)
    if p[i-1]<=mi and pp[k-1]==ma:
        count-=1
    elif pp[0]==mi and pp[k-1]==ma:
        pp_s=np.sort(pp)
        for i in range(len(pp)):
            if pp_s[i]!=pp[i]:
                break
            
            if i==len(pp)-1:
                if first==0:
                    first+=1
                else:
                    count-=1
                    

print(count)

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.copy(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:
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)
        ch = t[i:i+K]
        ch.sort()
        t[i:i+K] = ch
        ans.add(''.join(map(str, t)))

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import copy

[n,k] = list(map(int, input().split()))
P = list(map(int, input().split()))
store=[]

for i in range(n-k+1):
    Q=copy(P)
    a=Q[i:(i+k)]
    a=sorted(a)
    Q[i:(i+k)]=a
    
    new=True
    for j in store:
        if Q==j:
            new=False
            break;
    if new:
        store.append(Q)
ans=len(store)
print(ans)

Submission status: Time Limit Exceeded

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

'''
import random
N = 1000
K = 4
P = random.sample(list(range(N)),N)
#print("P",P)
'''

def simple():
	s = set({})
	for i in range(N-K+1):
		Q = tuple(P[:i]+sorted(P[i:i+K])+P[i+K:])
		s.add(Q)
	return len(s)

ans = 0
mi = -1 
sp = sorted(P[:K])
if sp != P[:K]:
	ans += 1
else:
	ans += 1
	mi += 1

for i in range(1,N-K+1):
	f = False
	if sp[0] != P[i-1]:
		f = True
	if sp[-1] > P[i+K-1]:
		f = True
	sp.remove(P[i-1])
	bisect.insort(sp,P[i+K-1])
	if f and sp == P[i:K+i]:
		mi += 1
	ans += int(f)
	#print(f,sp)
	#print(P[:i]+sp+P[K+i:])

ans -= max(0,mi)
#print(mi)
#print("ans",simple())
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
e = input().split()
num = int(e[0])
div = int(e[1])
array = list(map(int, input().split()))
box = []
for i in range(0,num-div+1):
  if i==0:
    result = list(np.sort(array[:div])) + array[div:]
  elif i<num-div:
    result = array[:i] + list(np.sort(array[i:i+div])) + array[i+div:]
  else:
    result = array[:div] + list(np.sort(array[div:]))
  box.append(result)
print(len(np.unique([str(x) for x in box])))

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]
f = False
cnt = 0
ccnt = 0
for i in range(N - K + 1):
  if P[i:i+K] == sorted((P[i:i+K])):
    ccnt += 1
    continue
  if f:
    if P[i+K-1] == max(P[i:i+K]):
      cnt += 1
  if P[i] == min(P[i:i+K]):
    f = True
  else:
    f = False
if ccnt > 1:
  cnt += ccnt - 1
print(N - K + 1 - cnt)

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[:i] + sorted(P[i : i+K]) + P[i+K : ]
    S.add(tuple(_))
print(len(S))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
P=[int(i) for i in input().split()]
num=2**(n-1).bit_length()
def init1(init_val):
  for i in range(n):
    seg1[i+num-1]=init_val[i]    
    for i in range(num-2,-1,-1) :
      seg1[i]=max(seg1[2*i+1],seg1[2*i+2]) 
def init2(init_val):
  for i in range(n):
    seg2[i+num-1]=init_val[i]    
    for i in range(num-2,-1,-1) :
      seg2[i]=min(seg2[2*i+1],seg2[2*i+2]) 
   
def query1(p,q):
  if q<=p:
    return ide_ele1
  p+=num-1
  q+=num-2
  res=ide_ele1
  while q-p>1:
    if p&1==0:
      res=max(res,seg1[p])
    if q&1==1:
      res=max(res,seg1[q])
      q-=1
    p=p//2
    q=(q-1)//2
  if p==q:
    res=max(res,seg1[p])
  else:
    res=max(max(res,seg1[p]),seg1[q])
  return res
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=min(res,seg2[p])
    if q&1==1:
      res=min(res,seg2[q])
      q-=1
    p=p//2
    q=(q-1)//2
  if p==q:
    res=min(res,seg2[p])
  else:
    res=min(min(res,seg2[p]),seg2[q])
  return res
ide_ele1=0
ide_ele2=n
seg1=[ide_ele1]*2*num
seg2=[ide_ele2]*2*num
init1(P)
init2(P)
ans=1
for i in range(k,n):
  if P[i-k]==query2(i-k,k+1) and P[i]==query1(i-k,k+1):
    continue
  else:
    ans+=1

Q=[0]*n
for i in range(1,n):
  if P[i]>P[i-1]:
    Q[i]=Q[i-1]+1
  else:
    continue
count=0
for i in range(n):
  if Q[i]>=k-1:
    count+=1
print(ans-max(0,count-1))

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):
    left = P[:i]
    X = P[i : i + K]
    right = P[i + K:]
    X.sort()
    X = left + X + right
    S.append(X)
seen = []
S = [x for x in S if x not in seen and not seen.append(x)]
print(len(S))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())

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



fin_str=[]
for a in range(N-M+1):
    hoge=A[:a]+sorted(A[a:a+M])+A[a+M:]
    
    fin_str.append("".join(list(map(str,hoge))))


print(len(set(fin_str)))

Submission status: Time Limit Exceeded

Solution code:

from sys import stdin
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 = copy.copy(Ps[i:i+K])
    com = copy.copy(Ps)
    test.sort()
    com[i:i+K] = test
    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 = map(int, input().split())
P = list(map(int, input().split()))
sortList = []
for i in range(N-K+1):
    tmpList = P[i:i+K]
    tmpWholeList = P[:]
    tmpWholeList[i:i+K] = sorted(tmpList)
    sortList.append(''.join(map(str, tmpWholeList)))


setList = list(set(sortList))
print(len(setList))

Submission status: Time Limit Exceeded

Solution code:
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value, N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                self.node[i] = left_i
            else:
                self.node[i] = right_i

    def set_input(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                new_i = left_i
            else:
                new_i = right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def get_input(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def get_output(self, a=0, b=-1):
        return self.get_input(self.get_output_index(a,b))

    def get_output_index(self,
                         a=0, b=-1,
                         k=0, l=0, r=-1):
        if b < 0:
            b = self.N
        if r < 0:
            r = self.N
        if a <= l and r <= b:
            return self.node[k]
        elif r <= a or b <= l:
            return None
        else:
            left_i = self.get_output_index(a,b,2*k+1,l,(l+r)//2)
            right_i = self.get_output_index(a,b,2*k+2,(l+r)//2,r)
            left_v, right_v = self.get_input(left_i), self.get_input(right_i)
            if left_v is None and right_v is None:
                return None
            elif self.comp(left_v, right_v):
                return left_i
            else:
                return right_i

def get_sequence(arr):
    if len(arr) == 0:
        return [], []
    elements = []
    nums = []
    n = 1
    prev = arr[0]
    for c in arr[1:]:
        if c == prev:
            n += 1
        else:
            elements.append(prev)
            nums.append(n)
            prev = c
            n = 1
    elements.append(prev)
    nums.append(n)
    return elements, nums

N, K = inpl()
P = inpl()
minseg = SegmentTree(P)
maxseg = SegmentTree(P, reverse=True)

ans = 1
for i in range(N-K):
    if P[i] < minseg.get_output(i+1,i+K) and P[i+K] > maxseg.get_output(i+1,i+K):
        pass
    else:
        ans += 1

ordered = [ P[i] < P[i+1] for i in range(N-1)]
_, nums = get_sequence(ordered)
unchanged = len(list(filter(lambda x: x>=K-1, nums)))
if unchanged > 1:
    ans -= unchanged-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())

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

fin_str=[]
for a in range(N-M+1):
    hoge=A[:a]+sorted(A[a:a+M])+A[a+M:]
    
    fin_str.append("".join(list(map(str,hoge))))


print(len(set(fin_str)))

Submission status: Time Limit Exceeded

Solution code:
def insert(target_list, target):
  for i in range(len(target_list) - 1):
    if target_list[i] < target and target < target_list[i+1]:
      target_list.insert(i+1, target)
      return
  target_list.append(target)

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

res_set = set()

target = []
for i in range(N - K + 1):
  if i == 0:
    target = P[i:i+K]
    target.sort()
  else:
    target.remove(P[i-1])
    insert(target, P[i+K-1])
  #print(target)
  new_list = P[:i] + target + P[i+K:]
  res_set.add(''.join(new_list))

#print(res_set)
print(len(res_set))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import numpy as np
n, k = map(int, input().split())
p = np.array(list(map(int, input().split())))
count = 1
flag = 0
esc = 0
for i in range(1, n):
    if flag < k-1:
        if p[i-1] < p[i]:
            flag += 1
        else:
            flag = 0
    else:
        flag = 0
    #print(flag)
    if flag == k-1:
        esc += 1
#print(esc)
if esc > 0:
    esc -= 1
        
for i in range(1, n - k + 1):
    sub = p[i:i+k]
    sub_max = list(-sub.copy())
    sub_min = list(sub.copy())
    heapq.heapify(sub_max)
    heapq.heapify(sub_min)
    #print(p[i+k-1])
    if sub_max[0] * -1 != p[i+k-1]:
        count += 1
        continue
    if sub_min[0] < p[i-1]:
        count += 1
        continue
print(count - esc)

Submission status: Time Limit Exceeded

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

s = set()
 
for i in range(0, N - K + 1):
  string = "".join(P[0:i])
  string = string + "".join(sorted(P[i:i+K]))
  string = string + "".join(P[i+K:N])
  s.add(string)

print(len(s))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree():
    def __init__(self, values, merge_func=min, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        self.merge = merge_func
        while self.size < n:
            self.size *= 2
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [self.default] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])

    def update(self, index, value):
        index += self.size
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.merge(
                self.tree[index*2], self.tree[index*2+1])

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.default
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return self.merge(left, right)

    # query segmentation value of [a, b)
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    seq = 1
    for i in range(K-1):
        if P[i] < P[i+1]:
            seq += 1
        else:
            seq = 1
    has_orig = seq == K
    rmq = SegmentTree(P)
    rMq = SegmentTree(P, merge_func=max, default=-1)
    ans = 1
    for i in range(N-K):
        if P[i+K-1] < P[i+K]:
            seq += 1
        else:
            seq = 1
        if seq >= K:
            if not has_orig:
                has_orig = True
                ans += 1
            continue
        mn = rmq.query(i, i+K+1)
        mx = rMq.query(i, i+K+1)
        if P[i] != mn or P[i+K] != mx:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
e = input().split()
num = int(e[0])
div = int(e[1])
array = list(map(int, input().split()))
box = []
turn = num-div+1
for i in range(0,turn):
  if i==0:
    a = array[:div]
    b = array[div:]
    result = list(np.sort(a)) + b
  elif i<turn-1:
    a = array[:i]
    b = array[i:i+div]
    c = array[i+div:]
    result = a + list(np.sort(b)) + c
  else:
    a = array[:div]
    b = array[div:]
    result = a + list(np.sort(b))
  box.append(result)
print(len(np.unique([str(x) for x in box])))

Submission status: Time Limit Exceeded

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

l = len(p)
lis = []

for i in range(l- k + 1):
  q = p[:i] + sorted(p[i:i+k]) + p[i+k:]
  if not q in lis:
    lis.append(q)
   
print(len(lis))