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 sys
input = sys.stdin.readline
n, k = map(int, input().split())
P = list(map(int, input().split()))

INF = 2**31 - 1
N0 = 1 << (n-1).bit_length()
seg_min = [INF]*(N0 << 1)
seg_max = [0]*(N0 << 1)

def update_min(i, x):
    i += N0
    seg_min[i] = x
    while i > 1:
        y = seg_min[i ^ 1]
        if y <= x:
            break
        i >>= 1
        seg_min[i] = x
            
def query_min(l, r):
    res = INF
    l += N0
    r += N0
    while l < r:
        if r & 1:
            res = min(res, seg_min[r-1])
        if l & 1:
            res = min(res, seg_min[l])
            l += 1
        l >>= 1
        r >>= 1
 
    return res

def init_min(original):
    for i, x in enumerate(original):
        update_min(i, x)
        
def update_max(i, x):
    i += N0
    seg_max[i] = x
    while i > 1:
        y = seg_max[i ^ 1]
        if y >= x:
            break
        i >>= 1
        seg_max[i] = x
            
def query_max(l, r):
    res = 0
    l += N0
    r += N0
    while l < r:
        if r & 1:
            res = max(res, seg_max[r-1])
        if l & 1:
            res = max(res, seg_max[l])
            l += 1
        l >>= 1
        r >>= 1
 
    return res

def init_max(original):
    for i, x in enumerate(original):
        update_max(i, x)
        
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

init_min(P)
init_max(P)

uf = UnionFind(n-k+1)

for i in range(n-k):
  m = query_min(i, i+k+1)
  M = query_max(i, i+k+1)
  if m == P[i] and M == P[i+k]:
    uf.unite(i, i+1)

q = -1
s = 0
for i in range(k-1):
  if P[i] < P[i+1]:
    s += 1
if s == k-1:
  q = 0
for i in range(n-k):
  s -= int(P[i] < P[i+1])
  s += int(P[i+k-1] < P[i+k])
  if s == k-1:
    if q == -1:
      q = i+1
    else:
      uf.unite(q, i+1)
ans = uf.group_count()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, N, f, e=None):
        self.N = 1<<(N-1).bit_length()
        self.seg = [e] * (self.N*2)
        self.e = e
        self.f = f

    def build(self, A):
        for i,a in enumerate(A):
            self.seg[i+self.N] = a
        for i in range(self.N-1,0,-1):
            self.seg[i] = self.f(self.seg[i<<1], self.seg[i<<1|1])

    def update(self, i, x): # a_i += x
        i += self.N
        self.seg[i] = x
        while i > 1:
            self.seg[i>>1] = self.f(self.seg[i], self.seg[i^1])
            i >>= 1

    def query(self, a, b): # f [a, b)
        L = R = self.e
        a += self.N
        b += self.N
        while a < b:
            if a&1:
                L = self.f(L, self.seg[a])
                a += 1
            if b&1:
                b -= 1
                R = self.f(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.f(L, R)

from collections import Counter
def main():
    N,K,*P=map(int, open(0).read().split())
    Mseg=SegmentTree(N, max, 0)
    mseg=SegmentTree(N, min, float("inf"))
    Mseg.build(P)
    mseg.build(P)
    D=Counter(P[:K])
    ans=1
    als=1
    for i in range(1,K):
        als=als+1 if P[i]>P[i-1] else 1
    iss=als==K
    for i in range(N-K):
        als=als+1 if P[i+K]>P[i+K-1] else 1
        mp=mseg.query(i, i+K)
        Mp=Mseg.query(i+1,i+K+1)
        if not (mp==P[i] and Mp==P[i+K]) and not (iss and als==K):
            ans+=1
        iss|=als==K
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def twopowerceil(n):  # return m s.t. m>=n and m=2**p
    for i in range(40):
        m = 2**i
        if m >= n:
            return m
    return -1

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

def segtreemininit(a,n):  # upto N-1, not N
    global mintree,maxtree
    nn = twopowerceil(n)
    mintree = [BIG]*(2*nn)
    for i in range(n):
        mintree[nn-1+i] = a[i]
    for i in range(nn-2,-1,-1):
        mintree[i] = min(mintree[2*i+1], mintree[2*i+2])

def segtreemin(x,y,n):
    nn = twopowerceil(n)
    return segtreemincore(x,y,0,0,nn)

def segtreemincore(x,y,k,l,r):
    if r<=x or y<=l:
        return BIG
    if x<=l and r<=y:
        return mintree[k]
    vl = segtreemincore(x,y,2*k+1,l,(l+r)//2)
    vr = segtreemincore(x,y,2*k+2,(l+r)//2,r)
    return min(vl,vr)

# # # #

def segtreemaxinit(a,n):  # upto N-1, not N
    global maxtree
    nn = twopowerceil(n)
    maxtree = [-BIG]*(2*nn)
    for i in range(n):
        maxtree[nn-1+i] = a[i]
    for i in range(nn-2,-1,-1):
        maxtree[i] = max(maxtree[2*i+1], maxtree[2*i+2])

def segtreemax(x,y,n):
    nn = twopowerceil(n)
    return segtreemaxcore(x,y,0,0,nn)

def segtreemaxcore(x,y,k,l,r):
    if r<=x or y<=l:
        return -BIG
    if x<=l and r<=y:
        return maxtree[k]
    vl = segtreemaxcore(x,y,2*k+1,l,(l+r)//2)
    vr = segtreemaxcore(x,y,2*k+2,(l+r)//2,r)
    return max(vl,vr)


n,k = inm()
a = inl()

segtreemininit(a,n)
segtreemaxinit(a,n)

st = 1
kstrkscnt = 0
kstrks = [False]*n
for i in range(n-1):
    if a[i]<a[i+1]:
        st += 1
        if st>=k:
            kstrkscnt += 1
            kstrks[i+1] = True
    else:
        st = 1

cnt = 0
for i in range(n-k):
    if not kstrks[i+k-1] and a[i]<segtreemin(i+1,i+k,n) \
       and not kstrks[i+k] and segtreemax(i+1,i+k,n)<a[i+k]:
       cnt += 1

if kstrkscnt>0:
    kstrkscnt -= 1
print(n-k+1-kstrkscnt-cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int,input().split())
P = list(map(int,input().split()))
count = 0
first = 1

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

Submission status: Time Limit Exceeded

Solution code:
class SWAG():
    def __init__(self,unit,f):
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        self.f=f
    def __refill_right(self):
        temp=[]
        n=len(self.data_l)
        *_,=map(temp.append,(self.popleft()for _ in range(n//2)))
        *_,=map(self.append,(self.popleft()for _ in range(n//2,n)))
        *_,=map(self.appendleft,temp[::-1])
    def __refill_left(self):
        temp=[]
        n=len(self.data_r)
        *_,=map(temp.append,(self.pop()for _ in range(n//2)))
        *_,=map(self.appendleft,(self.pop()for _ in range(n//2,n)))
        *_,=map(self.append,temp[::-1])
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__refill_right()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__refill_left()
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min)
s_max=SWAG(0,max)
*_,=map(s_min.append,p[:k-1])
*_,=map(s_max.append,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Submission status: Time Limit Exceeded

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

#リストを文字列化する方法
#''.join(map(str,p))

num_list = []
ans = 0

for i in range(n-k+1):
	tmp = p[i:i+k]
	tmp.sort()
	string1 = ''.join(map(str,p[:i]))
	string2 = ''.join(map(str,tmp))
	string3 = ''.join(map(str,p[i+k:]))
	string = string1+string2+string3
	if string not in num_list:
		num_list.append(string)
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
P = list(map(int,input().split()))
q1, q2 = [], []
if N == K:
    print(1)
    exit()
res = 0
r = 0
for i in range(N):
    while q1 and P[q1[-1]] < P[i]:
        q1.pop()
    while q2 and P[q2[-1]] > P[i]:
        q2.pop()
    q1.append(i)
    q2.append(i)
    if q1[0] <= i - K:
        q1.pop(0)
    if q2[0] <= i - K:
        q2.pop(0)
    if i > 0 and P[i - 1] < P[i]:
        x = min(x + 1, K - 1)
    else:
        x = 0
    if i == K - 1 or (i >= K and not (P[i - K] < P[q2[0]] and q1[0] == i)):
        if x != K - 1:
            r += 1
        else:
            res = 1
    # if i >= K - 1:
    #     if P[i-K+1] == P[q1[0]] and P[i] == P[q2[0]]:
    #         continue
    #     else:
    #         res += 1
print(r+1 if res else r)

Submission status: Time Limit Exceeded

Solution code:
class MinSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p

    def put(self,pos):
        val = self.val_list[pos]

        while len(self.pos_list) > 0:
            pos1 = self.pos_list[-1]
            val1 = self.val_list[pos1]
            if val1 >= val:
                del self.pos_list[-1]
            else:
                break
        self.pos_list.append(pos)

    def get(self,pos):
        while len(self.pos_list) > 0:
            pos1 = self.pos_list[0]
            if pos1 <= pos:
                del self.pos_list[0]
            else:
                break

    def min(self):
        pos1 = self.pos_list[0]
        val1 = self.val_list[pos1]
        return val1

class MaxSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p

    def put(self,pos):
        val = self.val_list[pos]

        while len(self.pos_list) > 0:
            pos1 = self.pos_list[-1]
            val1 = self.val_list[pos1]
            if val1 <= val:
                del self.pos_list[-1]
            else:
                break
        self.pos_list.append(pos)

    def get(self,pos):
        while len(self.pos_list) > 0:
            pos1 = self.pos_list[0]
            if pos1 <= pos:
                del self.pos_list[0]
            else:
                break

    def max(self):
        pos1 = self.pos_list[0]
        val1 = self.val_list[pos1]
        return val1




s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 1
ident = True
rv_pos = -1

minw = MinSlideWindow(p)
maxw = MaxSlideWindow(p)

for i in range(k - 1):
    if p[i] > p[i + 1]:
        rv_pos = i
        ident = False
    
for i in range(k-1):
    minw.put(i)
    maxw.put(i)

for i in range(1,n - k + 1):
    
    maxw.put(i + k - 2)
    minw.put(i + k - 2)
    maxw.get(i-1)
    minw.get(i-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 p[i + k - 2] > p[i + k - 1]:
        rv_pos = i + k - 2
        

    
    if rv_pos < i:
        if not ident:
            ident = True
            num += 1
        continue
            

    if p[i - 1] > minw.min() or p[i + k - 1] < maxw.max():
        num += 1

    
print(num)

Submission status: Time Limit Exceeded

Solution code:
class MinSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p

    def put(self,pos):
        val = self.val_list[pos]

        while len(self.pos_list) > 0:
            pos1 = self.pos_list[-1]
            val1 = self.val_list[pos1]
            if val1 >= val:
                del self.pos_list[-1]
            else:
                break
        self.pos_list.append(pos)

    def get(self,pos):
        while len(self.pos_list) > 0:
            pos1 = self.pos_list[0]
            if pos1 <= pos:
                del self.pos_list[0]
            else:
                break

    def min(self):
        pos1 = self.pos_list[0]
        val1 = self.val_list[pos1]
        return val1

class MaxSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p

    def put(self,pos):
        val = self.val_list[pos]

        while len(self.pos_list) > 0:
            pos1 = self.pos_list[-1]
            val1 = self.val_list[pos1]
            if val1 <= val:
                del self.pos_list[-1]
            else:
                break
        self.pos_list.append(pos)

    def get(self,pos):
        while len(self.pos_list) > 0:
            pos1 = self.pos_list[0]
            if pos1 <= pos:
                del self.pos_list[0]
            else:
                break

    def max(self):
        pos1 = self.pos_list[0]
        val1 = self.val_list[pos1]
        return val1





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
before_sort = False
minw = MinSlideWindow(p)
maxw = MaxSlideWindow(p)

before_sort_i = 0

for i in range(k - 2):
    minw.put(i)
    maxw.put(i)

for i in range(n - k + 1):

    maxw.put(i + k - 2)
    maxw.get(i-1)
    minw.put(i + k - 2)
    minw.get(i-1)

    
    if before_sort:
        if p[i + k - 1] < p[i + k - 2]:
            num += 1
            before_sort = False 
        else:
            before_sort_i += 1
        continue
    
    else:
        if before_sort_i + k <= i or i <= k:
            for j in range(k - 1):
                if p[i + j] > p[i + j +1]:
                    break
            else:
                if not ident:
                    ident = True
                    num += 1
                before_sort = True
                before_sort_i = i
                continue

            if i == 0:
                num += 1
                continue

            if p[i - 1] > minw.min() or p[i + k - 1] < maxw.max():
                num += 1  
        
        else:
            if p[i - 1] > minw.min() or p[i + k - 1] < maxw.max():
                num += 1
            if p[i + k - 1] <p[i + k - 2]:
                before_sort_i = i - 1
    

print(num)

Submission status: Time Limit Exceeded

Solution code:
class MinSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p

    def put(self,pos):
        val = self.val_list[pos]

        while len(self.pos_list) > 0:
            pos1 = self.pos_list[-1]
            val1 = self.val_list[pos1]
            if val1 >= val:
                del self.pos_list[-1]
            else:
                break
        self.pos_list.append(pos)

    def get(self,pos):
        while len(self.pos_list) > 0:
            pos1 = self.pos_list[0]
            if pos1 <= pos:
                del self.pos_list[0]
            else:
                break

    def min(self):
        pos1 = self.pos_list[0]
        val1 = self.val_list[pos1]
        return val1

class MaxSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p

    def put(self,pos):
        val = self.val_list[pos]

        while len(self.pos_list) > 0:
            pos1 = self.pos_list[-1]
            val1 = self.val_list[pos1]
            if val1 <= val:
                del self.pos_list[-1]
            else:
                break
        self.pos_list.append(pos)

    def get(self,pos):
        while len(self.pos_list) > 0:
            pos1 = self.pos_list[0]
            if pos1 <= pos:
                del self.pos_list[0]
            else:
                break

    def max(self):
        pos1 = self.pos_list[0]
        val1 = self.val_list[pos1]
        return val1




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

minw = MinSlideWindow(p)
maxw = MaxSlideWindow(p)

for i in range(k-2):
    minw.put(i)
    maxw.put(i)

for i in range(n - k + 1):
 
    maxw.put(i + k - 2)
    maxw.get(i-1)
    minw.put(i + k - 2)
    minw.get(i-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

    if p[i - 1] > minw.min() or p[i + k - 1] < maxw.max():
        num += 1

print(num)

Submission status: Time Limit Exceeded

Solution code:
#B
#入力
N,K=map(int, input().split())
P=list(map(int,input().split()))
x=N-K+1
#処理
X=[P for i in range(x)]

#並び替えた順列を生成
for i in range(x):
    X[i]=X[i][:i]+sorted(X[i][i:i+K])+X[i][i+K:]

#重なりの判定
y=0
while len(X)!=0:
    z=len(X)
    X=[i for i in X if i != X[0]]

    y+=1
print(y)

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
before_sort = False
M = max(p[:k])
m = min(p[:k])

before_sort_i = 0

for i in range(n - k + 1):
    if before_sort:
        if p[i + k - 1] < p[i + k - 2]:
            M = p[i + k - 2]
            num += 1
            before_sort = False 
        else:
            M = p[i + k - 1]
            before_sort_i += 1
        m = p[i]
        continue
    
    else:
        if before_sort_i + k <= i or i <= k:
            for j in range(k - 1):
                if p[i + j] > p[i + j +1]:
                    break
            else:
                if M == p[i - 1] or M < p[i + k - 2]:
                    M = max(p[i:i + k - 1])
                if m == p[i - 1] or m > p[i + k - 2]:
                    m = min(p[i:i + k - 1])

                if not ident:
                    ident = True
                    num += 1
                before_sort = True
                before_sort_i = i
                continue

            if i == 0:
                num += 1
                continue

            if M == p[i - 1] or M < p[i + k - 2]:
                M = max(p[i:i + k - 1])
            if m == p[i - 1] or m > p[i + k - 2]:
                m = min(p[i:i + k - 1])
                
            if p[i - 1] > m or p[i + k - 1] < M:
                num += 1  
        
        else:
            if M == p[i - 1] or M < p[i + k - 2]:
                M = max(p[i:i + k - 1])
            if m == p[i - 1] or m > p[i + k - 2]:
                m = min(p[i:i + k - 1])
                
            if p[i - 1] > m or p[i + k - 1] < M:
                num += 1
            if p[i + k - 1] <p[i + k - 2]:
                before_sort_i = i - 1
    

print(num)

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
before_sort = False
M = max(p[:k])
m = min(p[:k])

before_sort_i = 0

for i in range(n - k + 1):
    if before_sort:
        if p[i + k - 1] < p[i + k - 2]:
            M = p[i + k - 2]
            num += 1
            before_sort = False 
        else:
            M = p[i + k - 1]
            before_sort_i += 1
        m = p[i]
        continue
    
    else:
        if before_sort_i + k <= i or i <= k:
            for j in range(k - 1):
                if p[i + j] > p[i + j +1]:
                    break
            else:
                if M == p[i - 1] or M < p[i + k - 2]:
                    M = max(p[i:i + k - 1])
                if m == p[i - 1] or m > p[i + k - 2]:
                    m = min(p[i:i + k - 1])

                if not ident:
                    ident = True
                    num += 1
                before_sort = True
                before_sort_i = i
                continue

            if i == 0:
                num += 1
                continue

            if M == p[i - 1] or M < p[i + k - 2]:
                M = max(p[i:i + k - 1])
            if m == p[i - 1] or m > p[i + k - 2]:
                m = min(p[i:i + k - 1])
                
            if p[i - 1] > m or p[i + k - 1] < M:
                num += 1  
        
        else:
            if M == p[i - 1] or M < p[i + k - 2]:
                M = max(p[i:i + k - 1])
            if m == p[i - 1] or m > p[i + k - 2]:
                m = min(p[i:i + k - 1])
                
            if p[i - 1] > m or p[i + k - 1] < M:
                num += 1       
    

print(num)

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
before_sort = False
M = max(p[:k])
m = min(p[:k])

before_sort_i = 0

for i in range(n - k + 1):
    if before_sort:
        if p[i + k - 1] < p[i + k - 2]:
            M = p[i + k - 2]
            num += 1
            before_sort = False 
        else:
            M = p[i + k - 1]
            before_sort_i += 1
        m = p[i]
        continue
    
    else:
        if before_sort_i <= i + k:
            for j in range(k - 1):
                if p[i + j] > p[i + j +1]:
                    break
            else:
                if M == p[i - 1] or M < p[i + k - 2]:
                    M = max(p[i:i + k - 1])
                if m == p[i - 1] or m > p[i + k - 2]:
                    m = min(p[i:i + k - 1])

                if not ident:
                    ident = True
                    num += 1
                before_sort = True
                before_sort_i = i
                continue

            if i == 0:
                num += 1
                continue

            else:
                if M == p[i - 1] or M < p[i + k - 2]:
                    M = max(p[i:i + k - 1])
                if m == p[i - 1] or m > p[i + k - 2]:
                    m = min(p[i:i + k - 1])
    
                if p[i - 1] > m or p[i + k - 1] < M:
                    num += 1       
    

print(num)

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
so = False
M = max(p[:k])
m = min(p[:k])


for i in range(n - k + 1):
    if so:
        if p[i + k - 1] < p[i + k - 2]:
            M = p[i + k - 2]
            num += 1
            so = False
        else:
            M = p[i + k - 1]
        m = p[i]
        continue
    
    else:
        for j in range(k - 1):
            if p[i + j] > p[i + j +1]:
                break
        else:
            if M == p[i - 1] or M < p[i + k - 2]:
                M = max(p[i:i + k - 1])
            if m == p[i - 1] or m > p[i + k - 2]:
                m = min(p[i:i + k - 1])

            if not ident:
                ident = True
                num += 1
            so = True
            continue

        if i == 0:
            num += 1
            continue

        else:
            if M == p[i - 1] or M < p[i + k - 2]:
                M = max(p[i:i + k - 1])
            if m == p[i - 1] or m > p[i + k - 2]:
                m = min(p[i:i + k - 1])
    
            if p[i - 1] > m or p[i + k - 1] < M:
                num += 1       
    

print(num)

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
M = max(p[:k])
m = min(p[:k])


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
    else:
        if p[i - 1] > min(p[i:i + k - 1]) or p[i + k - 1] < max(p[i:i + k - 1]):
            num += 1      
    

print(num)

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
M = max(p[:k])
m = min(p[:k])


for i in range(n - k + 1):
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break
    else:
        if M == p[i - 1] or M < p[i + k - 2]:
            M = max(p[i:i + k - 1])
        if m == p[i - 1] or m > p[i + k - 2]:
            m = min(p[i:i + k - 1])

        if not ident:
            ident = True
            num += 1
        continue

    if i == 0:
        num += 1
        continue

    else:
        if M == p[i - 1] or M < p[i + k - 2]:
            M = max(p[i:i + k - 1])
        if m == p[i - 1] or m > p[i + k - 2]:
            m = min(p[i:i + k - 1])
    
        if p[i - 1] > m or p[i + k - 1] < M:
            num += 1      
    

print(num)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import bisect
from collections import deque

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

ans = 0
Q = [-x for x in P[:K]]
Q.sort()
D = deque([x for x in P[:K]])
oc = 0
ordered_twice = False

for i in range(len(D) - 1):
    if D[i] <= D[i + 1]:
        oc += 1

for i in range(N - K + 1):
    if i == 0:
        ans += 1
        if oc == K - 1:
            ordered_twice = True
    else:
        D.popleft()
        D.append(P[i + K - 1])
        if P[i - 1] <= D[0]:
            oc -= 1
        if D[K - 2] <= D[K - 1]:
            oc += 1
        if oc == K - 1:
            if not ordered_twice:
                ordered_twice = True
                if -P[i - 1] != Q[-1] or Q[0] < -P[i + K - 1]:
                    ans += 1
            if -P[i - 1] == Q[-1]:
                Q.pop()
            bisect.insort_left(Q, -P[i + K - 1])
        else:
            if -P[i - 1] != Q[-1] or Q[0] < -P[i + K - 1]:
                ans += 1
            if -P[i - 1] == Q[-1]:
                Q.pop()
            bisect.insort_left(Q, -P[i + K - 1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy
N, K = map(int,input().split(' '))
P = np.array(list(map(int,input().split(' '))))
ans = []
q = np.sort(P[0:K])
p = copy.deepcopy(P)
p[0:K] = q
ans.append(p)
for i in range(1,N-K+1):
  flag = True
  q = np.sort(P[i:i+K])
  p = copy.deepcopy(P)
  p[i:i+K] = q
  for j in range(len(ans)):
    if all(p == ans[j]):
      flag = False 
      break
  if flag:ans.append(p)
print(len(ans))

Submission status: Time Limit Exceeded

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

m = min(P[ : K])
M = max(P[ : K])
for i in range(N-K):
    if m == P[i]:
        if M < P[i+K]:
            M = P[i+K]
            m = min(P[i+1 : i+K])
            continue
        else:
            M = max(P[i+1:i+K])
            m = min(P[i+1 : i+K+1])
    else:
        m = min(P[i+1 : i+K+1])
        M = max(P[i+1:i+K+1])
    if P[i:i+K] == sorted(P[i:i+K]):
        if flg:
            pass
        else:
            flg=True
            count+=1
    else:
        count+=1
if not flg and P[-1*K:] != P[-1*K:].sort():
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class SparseTable:
    """
    構築 O(NlogN)、クエリ O(1)
    """

    def __init__(self, values, fn):
        """
        :param list values:
        :param callable fn: 結合則を満たす冪等な関数。min、max など。add はだめ
        """
        self._values = values
        self._fn = fn

        # SparseTable を構築
        # self._table[i][p]: [i, i+2^p) に fn を適用した結果の値のインデックス
        self._table = self._build(values, fn)

        # self._msb[i]: 最上位ビット; どの p を見るべきか
        self._msb = [0] * (len(values) + 1)
        for i in range(2, len(values) + 1):
            self._msb[i] = self._msb[i >> 1] + 1

    @staticmethod
    def _build(values, fn):
        # AtCoder の PyPy 2.4.0 では math.log2 が使えない
        size = int(math.log(len(values), 2)) + 1

        st = [[0] * size for _ in range(len(values))]
        for i in range(len(values)):
            st[i][0] = i
        for p in range(1, size):
            for i in range(len(values)):
                q = min(i + (1 << (p - 1)), len(values) - 1)
                l = st[i][p - 1]
                r = st[q][p - 1]
                if values[l] == fn(values[l], values[r]):
                    st[i][p] = l
                else:
                    st[i][p] = r
        return st

    def get(self, a, b):
        """
        半開区間 [a, b) に fn を適用した結果
        :param int a:
        :param int b:
        """
        if b <= a:
            return None
        p = self._msb[b - a]
        return self._fn(
            self._values[self._table[a][p]],
            self._values[self._table[b - (1 << p)][p]]
        )


N, K = list(map(int, sys.stdin.readline().split()))
P = list(map(int, sys.stdin.readline().split()))

dp = [1] * N
for i in range(1, N):
    if P[i - 1] < P[i]:
        dp[i] = dp[i - 1] + 1

# 全部昇順じゃない場合の答え
ans = N - K + 1

asc_cnt = 0
st_max = SparseTable(P, max)
st_min = SparseTable(P, min)
for r in range(K, N):
    l = r - K
    if st_min.get(l, r) == P[l] and st_max.get(l + 1, r + 1) == P[r]:
        # 出ていったのが最小値で、入ってきたのが最大値のとき、変わらない
        ans -= 1
    elif dp[r] >= K:
        # すでに昇順
        ans -= 1
        asc_cnt += 1
if dp[K - 1] >= K:
    # すでに昇順
    ans -= 1
    asc_cnt += 1

if asc_cnt > 0:
    # すでに昇順のやつは一度だけ数えていい
    ans += 1
print(ans)