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 copy

N, K = map(int, input().split())
original = list(map(int,input().split()))
list_sort = []
cnt = 0

for i in range(N-K+1):
    after = copy.deepcopy(original)
    after_pre = original
    after[i:i+K] = sorted(after_pre[i:i+K])

    if after in list_sort:
        continue
    else:
        list_sort.append(after)
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

aList = []
for i in range(N-K+1):
  nP = copy.deepcopy(P)
  nP[i:i+K] = sorted(P[i:i+K])
  aList.append(nP)

print(len(set(list(map(tuple,aList)))))

Submission status: Time Limit Exceeded

Solution code:
import copy

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

aList = []
for i in range(N-K+1):
  nP = copy.deepcopy(P)
  nP[i:i+K] = sorted(P[i:i+K])
  if nP not in aList:
  	aList.append(nP)

print(len(aList))

Submission status: Time Limit Exceeded

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False

for i in range(n - k + 1):
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break
    else:
        if not ident:
            ident = True
            num += 1
        continue

    if i == 0:
        num += 1
        continue

    for j in range(1,k):
        if p[i - 1] > p[i + j - 1] or p[i + k - 1] < p[i + j - 1]:
            num += 1
            break
    

print(num)

Submission status: Time Limit Exceeded

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

for i in range(n-k+1):
  m = p[0:i] + sorted(p[i:i+k]) + p[i+k:n]
  if l.count(m) == 1:
    continue
  l.append(m)
print(len(l))

Submission status: Time Limit Exceeded

Solution code:
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.dat = list(range(size))
        self.SIZE = [1] * size  # 0-indexed

    def find(self, x):
        dat = self.dat
        stack = [x]
        while True:
            y = stack[-1]
            if dat[y] != y:
                stack += [dat[y]]
            else:
                break
        for s in stack:
            dat[s] = y
        return y

    def unite(self, x, y):
        is_same = self.is_same
        find = self.find
        SIZE = self.SIZE
        dat = self.dat
        if not is_same(x, y):
            X, Y = find(x), find(y)
            SX, SY = SIZE[X], SIZE[Y]
            if SX > SY:
                m = dat[X] = Y
            else:
                m = dat[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.dat)
        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.dat)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def sol():
    n,k=map(int,input().split())
    p=list(map(int,input().split()))
    minp=[0]*(n-k+1)
    maxp=[0]*(n-k+1)
    q1=deque([0])
    q2=deque([0])
    for i in range(1,k):
        while p[q1[-1]]>p[i]:
            q1.pop()
            if len(q1)==0:
                break
        while p[q2[-1]]<p[i]:
            q2.pop()
            if len(q2)==0:
                break
        q1.append(i)
        q2.append(i)
    for i in range(n-k+1):
        minp[i]=p[q1[0]]
        maxp[i]=p[q2[0]]
        if i==n-k:
            break
        if q1[0]==i:
            q1.popleft()
        if q2[0]==i:
            q2.popleft()
        while p[q1[-1]]>p[i+k]:
            q1.pop()
            if len(q1)==0:
                break
        while p[q2[-1]]<p[i+k]:
            q2.pop()
            if len(q2)==0:
                break
        q1.append(i+k)
        q2.append(i+k)

    d=[False]*(n-k+1)
    d[0]=all(p[i]<p[i+1] for i in range(k-1))
    i=1
    while i<n-k+1:
        if p[i+k-2]>p[i+k-1]:
            i+=k-1
        else:
            if d[i-1]:
                d[i]=True
            else:
                if p[i]<p[i+1]:
                    d[i]=all(p[j]<p[j+1] for j in range(i,i+k-1))
            i+=1

    ans=int(any(d))
    if not d[0]:
        ans+=1
    for i in range(n-k):
        if d[i+1]:
            continue
        if not (p[i]==minp[i] and p[i+k]==maxp[i+1]):
            ans+=1

    print(ans)
sol()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,k=map(int,input().split())
p=list(map(int,input().split()))
minp=[0]*(n-k+1)
maxp=[0]*(n-k+1)
q1=deque([0])
q2=deque([0])
for i in range(1,k):
    while p[q1[-1]]>p[i]:
        q1.pop()
        if len(q1)==0:
            break
    while p[q2[-1]]<p[i]:
        q2.pop()
        if len(q2)==0:
            break
    q1.append(i)
    q2.append(i)
for i in range(n-k+1):
    minp[i]=p[q1[0]]
    maxp[i]=p[q2[0]]
    if i==n-k:
        break
    if q1[0]==i:
        q1.popleft()
    if q2[0]==i:
        q2.popleft()
    while p[q1[-1]]>p[i+k]:
        q1.pop()
        if len(q1)==0:
            break
    while p[q2[-1]]<p[i+k]:
        q2.pop()
        if len(q2)==0:
            break
    q1.append(i+k)
    q2.append(i+k)

d=[False]*(n-k+1)
d[0]=all(p[i]<p[i+1] for i in range(k-1))
i=1
while i<n-k+1:
    if p[i+k-2]>p[i+k-1]:
        i+=k-1
    else:
        if d[i-1]:
            d[i]=True
        else:
            if p[i]<p[i+1]:
                d[i]=all(p[j]<p[j+1] for j in range(i,i+k-1))
        i+=1

ans=int(any(d))
if not d[0]:
    ans+=1
for i in range(n-k):
    if d[i+1]:
        continue
    if not (p[i]==minp[i] and p[i+k]==maxp[i+1]):
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
sequence=[]
ans=N-K+1
for i in range(N-K+1):
    newlist=sorted(P[i:i+K])
    newP=P[:i]+newlist+P[i+K:]
    sequence.append(newP)
for i in range(N-K+1):
    for j in range(i+1,N-K+1):
        if sequence[i]==sequence[j]:
            ans-=1
        else:
            pass
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n - k + 1):
    Q= deepcopy(p)
   
    tmp = p[i:i+k] # Pの連続するKの要素を切り出してsort
    tmp.sort()
    for j in range(k):
        Q[i+j] = tmp[j] #sortしたものをPに戻す
    ans.append(Q)

ans=list(map(list, set(map(tuple, ans))))
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import copy

n,k = map(int,input().split())
p = list(map(int,input().split()))
l_list = []
ans = 1

tmp = copy.deepcopy(p)

l = tmp[:3]
l.sort()
l_list.append(l+tmp[3:])

for i in range(1,n-2):
	l = tmp[i:i+3]
	l.sort()
	l_list.append(tmp[:i] + l + tmp[i+3:])

	if l_list[i-1] == l_list[i]:
		continue
	else:
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
(n,k),p = [list(map(int, s.split())) for s in open(0)]
p = np.array(p)

p_isordered = p[1:]>p[:-1]
p_cumsum = p_isordered.cumsum()

ans = n - k + 1
no_change = False
if p_cumsum[k-2]==k-1:
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if (q.argmin()==0 and q.argmax()==k):
        ans -= 1
        dec = True
    
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N, K = map(int, input().split())
P = list(map(int, input().split()))
target = []

for i in range(N - K + 1):
    count = 0
    sort = sorted(P[i:i + K])
    if i == 0:
        comp = sort + P[i + K:]
        target.append(comp)
    elif i == N - K:
        comp = P[:i] + sort
    else:
        comp = P[:i] + sort + P[i + K:]
    for a in target:
        if comp != a:
            count += 1
    if len(target) == count:
        target.append(comp)
print(len(target))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
p = np.array(p)

p_isorder = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
for j in range(k-1):
    if not p_isorder[j]:
        break
else:
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if (q.argmin()==0 and q.argmax()==k):
        ans -= 1
        dec = True
    
    for j in range(k-1):
        if not p_isorder[i+j+1]:
            break
    else:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')

class SegmentTree:
    def __init__(self, size):
        self._size = (1 << size.bit_length())
        self._data = [INF] * (self._size * 2)

    def update(self, index, value):
        index += self._size - 1
        self._data[index] = value
        while index > 0:
            index = (index - 1) // 2
            self._data[index] = min(self._data[index * 2 + 1], self._data[index * 2 + 2])

    def __query(self, qLeft, qRight, node, left, right):
        if right <= qLeft or qRight <= left:
            return INF
        if qLeft <= left and right <= qRight:
            return self._data[node]

        leftVal = self.__query(qLeft, qRight, node * 2 + 1, left, (left + right) // 2)
        rightVal = self.__query(qLeft, qRight, node * 2 + 2, (left + right) // 2, right)
        return min(leftVal, rightVal)

    def query(self, left, right):
        return self.__query(left, right, 0, 0, self._size)

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

minTree = SegmentTree(N)
maxTree = SegmentTree(N)

for i, p in enumerate(P):
    minTree.update(i, p)
    maxTree.update(i, -p)

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

    if minTree.query(left, right) == P[left] and maxTree.query(left + 1, right + 1) == -P[right]:
        continue
    else:
        if seq >= K:
            if hasSame:
                continue
            else:
                hasSame = True
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N - K + 1):
    count = 0
    sort = sorted(P[i:i + K])
    if i == 0:
        comp = sort + P[i + K:]
        target.append(comp)
    elif i == N - K:
        comp = P[:i] + sort
    else:
        comp = P[:i] + sort + P[i + K:]
    for a in target:
        if comp != a:
            count += 1
    if len(target) == count:
        target.append(comp)
print(len(target))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
s=set([P[0]])
z=0
u = False
p=P[0]
for i in range(1,K):
    r=p
    p=P[i]
    if r < p:
        z+=1
    else:
        z=0
    s.add(p)
if z == K-1:
    u = True
c=1
for i in range(N-K):
    r=p
    p=P[K+i]
    q=P[i]
    if r < p:
        z+=1
    else:
        z=0
    if max(s) > p:
        if z >= K-1:
            c += 1 if u == False else 0
            u = True
        else:
            c+=1
    elif min(s) < q:
        if z >= K-1:
            c += 1 if u == False else 0
            u = True
        else:
            c+=1
    s.remove(P[i])
    s.add(p)
print(c)

Submission status: Time Limit Exceeded

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
par = [i for i in range(n)]
rank = [0 for _ in range(n)]
for i in range(n-1):
    if p[i] < p[i+1]:
        union(i,i+1)
lst = []
for i in range(n-k+1):
    if root(i) == root(i+k-1):
        lst.append(i)
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: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
set_P = set()
for i in range(N-K+1):
    set_P.add(''.join(map(str,P[:i]+sorted(P[i:i+K])+P[i+K:])))
print(len(set_P))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
# 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)

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 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 collections import deque
# 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)

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 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:
N,K = map(int,input().split())
if N == K:
    print(1)
    exit()
P = list(map(int,input().split()))
def chk(A):
    global flg
    MINa=A[0]
    for a in A:
        if a < MINa:
            return False
        MINa=a
    flg=True
    return True
count=0
flg=False
m = min(P[ : K])
M = max(P[ : K])
for i in range(N-K):
    if m == P[i] and M < P[i+K]:
        M = P[i+K]
        m = min(P[i+1 : i+K])
        continue
    else:
        m = min(P[i+1 : i+K+1])
        M = max(P[i+1 : i+K+1])
        if chk(P[i:i+K]):
            pass
        else:
            count+=1
if not chk(P[-1*K:]):
    count+=1
if flg:
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy
n, k = map(int, input().split())
p = [int(x) for x in input().split()]
pl = set()

for i in range(n-k+1):
    p2 = copy.deepcopy(p)
    p2[i:i+k] = sorted(p[i:i+k])
    pl.add(str(p2))
    
print(len(pl))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
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()))

n,k = MAP()
p = LIST()

count = 1
for i in range(n-k+1):
    pi = p[i:i+k]
    flag = True
    if i != 0:
        if minp < min(pi) and maxp < max(pi):
            flag = False
        if sorted(p[i:i+k]) == p[i:i+k]:
            flag = False  
        if flag:
            count +=1   
    else:
        if sorted(p[i:i+k]) != p[i:i+k]:
            count +=1
    maxp = max(pi)
    minp = min(pi)

res = 0
for i in range(n-k+1):
    if sorted(p[i:i+k]) == p[i:i+k]:
        res +=1

if res==0:
    print(count-1)
else:
    print(count)

Submission status: Time Limit Exceeded

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

lastminMatch = 0
count = 0
noChangeFlag = 0

import numpy as np

for i in range(N-K+1):
    nowList = A[i:K+i]
    if nowList == sorted(nowList):
        if noChangeFlag == 0:
            noChangeFlag = 1
            count += 1
        continue
    if lastminMatch==1 and np.argmax(nowList)==K-1:
        pass
    else:
        count += 1
            
    if np.argmin(nowList) == 0:
        lastminMatch = 1
    else:
        lastminMatch = 0
print(count)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
p = [int(i) for i in input().split()]
# print(p)
q = []
for i in range(n-k+1):
    # print(p[:i],p[i:i+k],p[i+k:])
    q += [tuple(p[:i] + sorted(p[i:i+k]) + p[i+k:])]
# print(q)
# print(set(q))
print(len(set(q)))

Submission status: Time Limit Exceeded

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

for i in range(n):
    if i+k < n:
        if p[i] <= min(p[i:i+k]) and p[i+k] >= max(p[i+1:i+k]):
            count += 1
        elif p[i:i+k] == sorted(p[i:i+k]):
            count += 1

print(n-k+1-count)

Submission status: Time Limit Exceeded

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
import itertools
from collections import deque
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)
N, K, *P = map(int, sys.stdin.read().split())
ans = 1
flag = 0
_ = P[:K]
d = deque(_)
dmax = max(_)
dmin = min(_)
inc = [1 if x < y else 0 for x, y in zip(P, P[1:])]
inc_cum = [0] + list(itertools.accumulate(inc))
F = [y - x == K - 1 for x, y in zip(inc_cum, inc_cum[K - 1:])]
if F[0]:
    flag = 1
for i in range(N - K):
    r = P[i+K]
    d.append(r)
    l = d.popleft()
    same = F[i+1]
    # print('i:' + str(i))
    # print('dmax:' + str(dmax))
    # print('dmin:' + str(dmin))
    # print('l:' + str(l))
    # print('r:' + str(r))
    # print('flag:' + str(flag))
    # print('same:' + str(same))
    if (dmax < r and dmin == l) or (flag and same):
        ans -= 1
    if same:
        flag = 1
    dmax = max(d) if l == dmax else max(r, dmax)
    dmin = min(d) if l == dmin else min(r, dmin)
    ans += 1
    # print('d:' + str(d))
print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
from collections import deque
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)
N, K, *P = map(int, sys.stdin.read().split())
ans = 1
_ = P[:K]
d = deque(_)
dmax = max(_)
dmin = min(_)
d2 = deque()
d3 = deque()
F = [0] * (N-K+1)
flag = 0
_old = P[0]
_new = 0
for i in range(N - 1):
    _old = _new
    _new = P[i + 1]
    tmp = '+' if _new - _old > 0 else '-'
    if i < K-1:
        d3.append(tmp)
    else:
        d2.append(tmp)
inc = d3.count('+')
if inc == K - 1:
    F[0] = 1
for i in range(N - K):
    # print('d3:' + str(d3))
    # print('d2:' + str(d2))
    # print('inc:' + str(inc))
    # print('K:' + str(K))
    new = deque.popleft(d2)
    d3.append(new)
    old = d3.popleft()
    if old == '-' and new == '+':
        inc += 1
    if old == '+' and new == '-':
        inc -= 1
    if inc == K - 1:
        F[i+1] = 1
# print('F:'+str(F))
if F[0]:
    flag = 1
for i in range(N - K):
    r = P[i+K]
    d.append(r)
    l = d.popleft()
    same = F[i+1]
    # print('i:' + str(i))
    # print('dmax:' + str(dmax))
    # print('dmin:' + str(dmin))
    # print('l:' + str(l))
    # print('r:' + str(r))
    # print('flag:' + str(flag))
    # print('same:' + str(same))
    if (dmax < r and dmin == l) or (flag and same):
        ans -= 1
    if same:
        flag = 1
    dmax = max(d) if l == dmax else max(r, dmax)
    dmin = min(d) if l == dmin else min(r, dmin)
    ans += 1
    # print('d:' + str(d))
print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
from collections import deque
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = 1
_ = P[:K]
d = deque(_)
dmax = max(_)
dmin = min(_)
d2 = deque()
d3 = deque()
F = [0] * (N-K+1)
flag = 0
_old = P[0]
_new = 0
for i in range(N - 1):
    _old = _new
    _new = P[i + 1]
    tmp = '+' if _new - _old > 0 else '-'
    if i < K-1:
        d3.append(tmp)
    else:
        d2.append(tmp)
inc = d3.count('+')
if inc == K - 1:
    F[0] = 1
for i in range(N - K):
    # print('d3:' + str(d3))
    # print('d2:' + str(d2))
    # print('inc:' + str(inc))
    # print('K:' + str(K))
    new = deque.popleft(d2)
    d3.append(new)
    old = d3.popleft()
    if old == '-' and new == '+':
        inc += 1
    if old == '+' and new == '-':
        inc -= 1
    if inc == K - 1:
        F[i+1] = 1
# print('F:'+str(F))
if F[0]:
    flag = 1
for i in range(N - K):
    r = P[i+K]
    d.append(r)
    l = d.popleft()
    same = F[i+1]
    # print('i:' + str(i))
    # print('dmax:' + str(dmax))
    # print('dmin:' + str(dmin))
    # print('l:' + str(l))
    # print('r:' + str(r))
    # print('flag:' + str(flag))
    # print('same:' + str(same))
    if (dmax < r and dmin == l) or (flag and same):
        ans -= 1
    if same:
        flag = 1
    dmax = max(d) if l == dmax else max(r, dmax)
    dmin = min(d) if l == dmin else min(r, dmin)
    ans += 1
    # print('d:' + str(d))
print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
from collections import deque
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = 1
_ = P[:K]
__ = sorted(_)
d = deque(_)
dmax = max(_)
dmin = min(_)
d2 = deque()
d3 = deque()
F = [0] * (N-K+1)
flag = 0
for i in range(N - 1):
    tmp = '+' if P[i + 1] - P[i] > 0 else '-'
    if i < K-1:
        d3.append(tmp)
    else:
        d2.append(tmp)
inc = d3.count('+')
if inc == K - 1:
    F[0] = 1
for i in range(N - K):
    # print('d3:' + str(d3))
    # print('d2:' + str(d2))
    # print('inc:' + str(inc))
    # print('K:' + str(K))
    new = deque.popleft(d2)
    d3.append(new)
    old = d3.popleft()
    if old == '-' and new == '+':
        inc += 1
    if old == '+' and new == '-':
        inc -= 1
    if inc == K - 1:
        F[i+1] = 1
# print('F:'+str(F))
if _ == __:
    flag = 1
for i in range(N - K):
    r = P[i+K]
    d.append(r)
    l = d.popleft()
    same = F[i+1]
    # print('i:' + str(i))
    # print('dmax:' + str(dmax))
    # print('dmin:' + str(dmin))
    # print('l:' + str(l))
    # print('r:' + str(r))
    # print('flag:' + str(flag))
    # print('same:' + str(same))
    if (dmax < r and dmin == l) or (flag and same):
        ans -= 1
    if same:
        flag = 1
    dmax = max(d) if l == dmax else max(r, dmax)
    dmin = min(d) if l == dmin else min(r, dmin)
    ans += 1
    # print('d:' + str(d))
print(str(ans))

Submission status: Time Limit Exceeded

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

out= deque()
l=len(P)
sp1=None

for n,p in enumerate(P):
    changed=None
    if n<=l-K:
        sp2=P[n:n+K]
        if sp1 is None or sp1 != sp2:
            s=sorted(sp2)
            if n==0:
                changed=s+P[n+K:]
            elif n==l-K:
                changed=P[0:n]+s
            else:
                changed=P[:n]+s+P[n+K:]
            if changed not in out:
                out.append(changed)
            sp1=sp2
        
print(len(out))

Submission status: Time Limit Exceeded

Solution code:
import copy
n, k = map(int, input().split(" "))
list_p = list(map(int, input().split(" ")))
list_p_change = []
for i in range(n - k + 1):
  sub_list = list_p[i:i+k]
  sub_list.sort()
  temp_list = copy.deepcopy(list_p)
  temp_list[i:i+k] = sub_list
  list_p_change.append(tuple(temp_list))
list_p_change_unique = list(set(list_p_change))
print(len(list_p_change_unique))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p = [int(p_ele) for p_ele in input().split()]
p_comp = [False for _ in range(n - 1)]
flag = False
for i in range(n - 1):
    if p[i] < p[i + 1]:
        p_comp[i] = True
buf = True
nonsort = False
ans = 0
for i in range(n - k + 1):
    flag = True
    for j in range(k - 1):
        flag = p_comp[i + j] and flag
    if flag:
        nonsort = True
        buf = True
    else:
        if buf:
            ans += 1
        else:
            flag = True
            for j in range(i, i + k-1):
                flag = flag and (p[i-1] < p[j] < p[i + k-1])
            if not flag:
                ans += 1
        buf = False
if nonsort:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
p = list(map(int,input().split()))
ng = []
c=0
for i in range(n-k+1):
    pick = p[i:i+k]
    pick.sort()
    dif = p[0:max(0,i)]+pick+p[min(n,i+k):]
    ##print(ng,dif,i,c)
    if ng.count(dif)==0:
        ng.append(dif)
        c+=1
print(c)

Submission status: Time Limit Exceeded

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

out={}
l=len(P)
sp1=None
for n,p in enumerate(P):
    changed=None
    if n<=l-K:
        sp2=P[n:n+K]
        if sp1 is None or sp1 != sp2:
            s=sorted(sp2)
            if n==0:
                changed=s+P[n+K:]
            elif n==l-K:
                changed=P[0:n]+s
            else:
                changed=P[:n]+s+P[n+K:]
            out["".join(map(str,changed))]=changed
            sp1=sp2
        
print(len(out))

Submission status: Time Limit Exceeded

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

out={}
l=len(P)
for n,p in enumerate(P):
    changed=None
    if n<=l-K:
        s=sorted(P[n:n+K])
        if n==0:
            changed=s+P[n+K:]
        elif n==l-K:
            changed=P[0:n]+s
        else:
            changed=P[:n]+s+P[n+K:]
        out["".join(map(str,changed))]=changed 

print(len(out))