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: Runtime Error

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

ans=0
for i in range(n-k):
  if min(P[i:i+k])==P[i:i+k][0] and P[i+k+1]==max(P[i:i+k+1]):
    ans-=1
  ans+=1
if ans==0:
  print(1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
P=[int(i) for i in input().split()]
n_max=2*10**5
num=n_max.bit_length()+1
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_max
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: Runtime Error

Solution code:
import bisect
n, k = map(int, input().split())
p = list(map(int, input().split()))
tmp = sorted(p[:k])
ans = 1
d = 0
#print(tmp)
for i in range(k-1,n-1):
  if p[i+1-k] == tmp[0] and p[i+1] > tmp[-1]:
    continue
  elif tmp == p[i+1-k:i+1]:
    d += 1
  else:
    ans += 1
  #print(p[i-k],i,k)
  tmp.remove(p[i+1-k])
  #print(tmp)
  tmp.insert(bisect.bisect_left(tmp, p[i+1]), p[i+1])
  #print(ans, tmp)
print(ans-max(0,d-1))

Submission status: Runtime Error

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 = Ps[i:i+K]
    test = sort(test)
    com = copy.copy(Ps)
    com[i:i+K] = testq
    if i == 0:
        lib.append(com)
        ans += 1
    else:
        if com in lib:
            None
        else:
            ans += 1
            lib.append(com)
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
P=[int(i) for i in input().split()]
n_max=2*10**5
num=n_max.bit_length()+1
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_max
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-count+1)

Submission status: Runtime Error

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

ans = 1
for i in range(1,N-K+1):
  S = P[i:i+K-1]
  if P[i-1] < min(S[:-1]) and P[i+K] > max(S[1:]):
    continue
  ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import pandas pd

num = int(input().split()[0])
div = int(input().split()[1])
array = list(map(int, input().split()))
box = []
 
for i in range(0,num-div+1):
  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: Runtime Error

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

count = 1
for i in range(1,N-K+1):
  y = -1
  z = N
  for h in range(K):
    y = max(y, p[h+i-1])
    z = min(z, p[h+i-1])
  if p[i-1] > z or  p[i+K]<y:
    count += 1
  
print(count)

Submission status: Runtime Error

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


#print(arr)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import pandas pd
 
input_data = input()
num = int(input_data[0].split()[0])
div = int(input_data[0].split()[1])
array = input_data[1].split()
array = [int(x) for x in array]
box = []
 
for i in range(0,num-div+1):
  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: Runtime Error

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


#print(arr)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

N, K = map(int, input().split())
ans = set()
nums = list(map(int, input().split()))
head = deque([])
tail = deque(nums[K:])
mid = deque(nums[:K])
ans.add("".join(map(str, head)) + "".join(map(str, sorted(list(mid)))) +"".join(map(str, tail)))

for i in range(K-1):
    head.append(mid.popleft())
    mid.append(tail.popleft())
    ans.add("".join(map(str, head)) + "".join(map(str, sorted(list(mid)))) +"".join(map(str, tail)))
print(len(ans))

Submission status: Runtime Error

Solution code:
N,K = [int(i) for i in input().split()]
data = [int(i) for i in input().split()]
point = 1
x = -1
y = data[0]
i = 0
m = 1
while i < len(data)-1:
    while x > y:
        m += 1
        i += 1
        x,y = y,data[i]
    if m != 1:
        point += m + min(m,K) - 3
    m = 1
    i += 1
    x,y = y,data[i]
print(point)

Submission status: Runtime Error

Solution code:
import numpy as np
import pandas pd

input_data = input()
num = input_data[0]
div = input_data[1]
array = input_data[2]
box = []

for i in range(0,num-div+1):
  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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)


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

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

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


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'))

size = N - K + 1
UF = list(range(size))
SIZE = [1] * size  # 0-indexed


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


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


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


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


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):
        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:
    unite(incK[0], i)

scan_uf()
print(len(set(UF)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)


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

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

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


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 = list(range(N - K + 1))
SIZE = [0] + [1] * N  # 1-indexed


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


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


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


def scan_uf():
    for i in range(len(UF)):
        find(i)


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):
        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:
    unite(incK[0], i)

scan_uf()
print(len(set(UF)))

Submission status: Runtime Error

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)

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

new_list = []
for i in range(len(p_list) - K + 1):
  p_list = 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: Runtime Error

Solution code:
h,w,a,b = map(int,input().split(" "))
matrix = list()
for i in range(h):
	matrix.append("")
if (w-a) < a or (h-b) < b :
  print("No")
  sys.exit()
matrix2 = list()
for line in matrix:
  line += "0" * a + "1" * (w-a)
  matrix2.append(line)
for i in range(1,h):
  p = matrix2[i][:i]
  matrix2[i] += p
  matrix2[i] = matrix2[i][i:]
for i in matrix2:
  print(i)

Submission status: Runtime Error

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


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 = list(range(N - K + 1))
SIZE = [0] + [1] * N  # 1-indexed


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


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


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


def scan_uf():
    for i in range(len(UF)):
        find(i)


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):
        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:
    unite(incK[0], i)

scan_uf()
print(len(set(UF)))

Submission status: Runtime Error

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

else:
  ans = N-K+1
  for i in range(len(P)):
    if i+K < N-1:
      small = P[i:i+K+1]
      small2 = P[i:i+K]
      if small[0] == min(small) and small[-1] == max(small):
        ans -= 1
      elif small2 == sorted(small2):
        ans -= 1
    
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
p = [int(i) for i in input().split()]
if N-K > 0:
    print(N-k)
else:
    print(1)

Submission status: Runtime Error

Solution code:
H,W,A,B=map(int,input().split())
a=[]
for i in range(H-1):
  for i in range(W-1):
    a+=[0]