Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Sliding Minimum Element

  For a given array $a_1, a_2, a_3, ... , a_N$ of $N$ elements and an integer $L$, find the minimum of each possible sub-arrays with size $L$ and print them from the beginning. For example, for an array $\{1, 7, 7, 4, 8, 1, 6\}$ and $L = 3$, the possible sub-arrays with size $L = 3$ includes $\{1, 7, 7\}$, $\{7, 7, 4\}$, $\{7, 4, 8\}$, $\{4, 8, 1\}$, $\{8, 1, 6\}$ and the minimum of each sub-array is 1, 4, 4, 1, 1 respectively.

Constraints

 $1 \leq N \leq 10^6$ 

 $1 \leq L \leq 10^6$

 $1 \leq a_i \leq 10^9$

 $L \leq N$ 

Input

The input is given in the following format.

$N$ $L$

$a_1$ $a_2$ ... $a_N$

Output

  Print a sequence of the minimum in a line. Print a space character between adjacent elements.

Sample Input 1

7 3
1 7 7 4 8 1 6

Sample Output 1

1 4 4 1 1



Sample input:
7 3
1 7 7 4 8 1 6


Sample output:
1 4 4 1 1

Submission status: Time Limit Exceeded

Solution code:
def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini :
            mini = A[i+L-1]
        elif A[i-1] == mini :
            mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini :
            mini = A[i]
        elif A[i+L] == mini:
            mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
ascend(0,N//2)
descend(N//2,N-L+1)

for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
N,L=map(int,input().split())
a=list(map(int,input().split()))
print(*[min(a[i:i+L])for i in range(N-L+1)])

Submission status: Time Limit Exceeded

Solution code:

n, l = map(int, input().split())

n_ = 1 # 実際に確保した配列のサイズ
while n_ < n:
  n_ *= 2

initv = pow(2, 31)-1
seg_tree = [initv for i in range(2*n_-1)]

def update(i, x):
  i += n_ - 1
  seg_tree[i] = x
  while i > 0 :
    i = int((i - 1)/2)
    seg_tree[i] = min(seg_tree[i*2+1], seg_tree[i*2+2])

def findMin(s, t):
  return query(s, t+1, 0, 0, n_)

def query(a, b, k, l, r):
  if r <= a or b <= l :
    return initv
  if a <= l and r <= b:
    return seg_tree[k]

  vl = query(a, b, k*2+1, l, int((l+r)/2))
  vr = query(a, b, k*2+2, int((l+r)/2), r)
  return min(vl, vr)

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

for i in range(n):
  update(i, series[i])

output = []

for i in range(n):

  output.append(findMin(i, i+l-1))

  if i+l == n:
    break

print(' '.join(map(str, output)))

Submission status: Time Limit Exceeded

Solution code:

n, l = map(int, input().split()) # 

n_ = 1 # actual size of array
while n_ < n:
  n_ *= 2

initv = pow(10, 9)
seg_tree = [initv for i in range(2*n_-1)]

def findMin(s, t):
  return query(s, t+1, 0, 0, n_)

def query(a, b, k, l, r):
  if r <= a or b <= l :
    return initv
  if a <= l and r <= b:
    return seg_tree[k]

  vl = query(a, b, k*2+1, l, int((l+r)/2))
  vr = query(a, b, k*2+2, int((l+r)/2), r)
  return min(vl, vr)


# take in input to segment tree
series = list(map(int, input().split()))
seg_tree[ n_-1 : n_+len(series)-1 ] = series[:]

# update segment tree
for i in range(n_-2, -1, -1):
  seg_tree[i] = min(seg_tree[i*2+1], seg_tree[i*2+2])


output = []

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

  output.append(findMin(i, i+l-1))

print(' '.join(map(str, output)))

Submission status: Time Limit Exceeded

Solution code:
import sys
#sys.setrecursionlimit(10000)
MAX = 2147483647

def initRMQ(n):
    n_ = 1

    while n_ < n:
        n_ *= 2

    for i in range(2*n_ - 1):
        D.append(MAX)

    return n_


def update(k, a):
    k += n_ - 1
    D[k] = a
    while k > 0:
        k = int((k - 1) / 2)
        D[k] = min(D[k*2 + 1], D[k*2 + 2])


def findMin(a, b):
    #for i in range(a, b): print(D[i+7], end=' ')
    return query(a, b, 0, 0, n_)


def query(a, b, k, l, r):
    #print('q', a, b, k, l, r)
    if r <= a or b <= l:
        return MAX

    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((l + r)/2))
    vr = query(a, b, k*2 + 2, int((l + r)/2), r)

    return min(vl, vr)


if __name__ == '__main__':
    n, l  = map(int, input().split())
    array = map(int, input().split())

    D = []
    n_ = initRMQ(n)

    for i, a in zip(range(n), array):
        update(i, a)

    for i in range(n-l):
        print(findMin(i, i+l), end=' ')

    print(findMin(n-l, n))

Submission status: Time Limit Exceeded

Solution code:
# Sliding Minimum Elements
INF = 2**31 - 1
[n, l] = list(map(int, input().split()))
data = list(map(int, input().split()))


def initRMQ(tree):
    global n
    size = 1
    while size < l:
        size *= 2
    i = 1
    while i <= 2*size - 1 - 1:
        tree.append(INF)
        i += 1
    n = size
    return tree

def update(k, a, temp):
    k += n - 1
    temp[k:k+l] = a
    for i in range(k, k+l, 2):
        while i > 0:
            i = int((i - 1)/2)
            temp[i] = min(temp[i*2 + 1], temp[i*2 + 2])


index = 0
array = initRMQ([INF])
while (len(data) - index - l) >= 0:
    temp = list(array)
    update(0, data[index:index+l], temp)
    index += 1
    if (len(data) - index - l) < 0:
        print(temp[0])
    else:
        print(temp[0], "", end="")

Submission status: Time Limit Exceeded

Solution code:
# Sliding Minimum Elements
INF = 2**31 - 1
[n, l] = list(map(int, input().split()))
data = list(map(int, input().split()))


def initRMQ(tree):
    global n
    size = 1
    while size < l:
        size *= 2
    i = 1
    while i <= 2*size - 1 - 1:
        tree.append(INF)
        i += 1
    n = size
    return tree

def update(k, a, temp):
    k += n - 1
    temp[k:k+l] = a
    for i in range(k, k+l, 2):
        while i > 0:
            i = int((i - 1)/2)
            temp[i] = min(temp[i*2 + 1], temp[i*2 + 2])


index = 0
array = initRMQ([INF])
while (len(data) - index - l) >= 0:
    #temp = list(array)
    #update(0, data[index:index+l], temp)
    temp = data[index:index+l]
    temp.sort()
    index += 1
    if (len(data) - index - l) < 0:
        print(temp[0])
    else:
        print(temp[0], "", end="")

Submission status: Time Limit Exceeded

Solution code:
import sys
MAX = 2147483647


def initRMQ(n):
    n_ = 1

    while n_ < n:
        n_ *= 2

    for i in range(2*n_ - 1):
        D.append(MAX)

    return n_


def update(k, a):
    k += n_ - 1
    D[k] = a
    while k > 0:
        k = int((k - 1) / 2)
        D[k] = min(D[k*2 + 1], D[k*2 + 2])


def findMin(a, b):
    return query(a, b, 0, 0, n_)


def query(a, b, k, l, r):
    #print('q', a, b, k, l, r)
    if r <= a or b <= l:
        return MAX

    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((l + r)/2))
    vr = query(a, b, k*2 + 2, int((l + r)/2), r)

    return min(vl, vr)


if __name__ == '__main__':
    n, l  = map(int, input().split())
    array = map(int, input().split())

    D = []
    n_ = initRMQ(n)

    for i, a in zip(range(n), array):
        update(i, a)

    #for i in range(n): print(D[i+n_-1], end=' ')
    #print()


    #for j in range(l): print(D[j+n_-1], end=' ')
    m = findMin(0, l)
    print(m, end='')

    for i in range(1, n-l+1):
        #for j in range(i, i+l): print(D[j+n_-1], end=' ')

        old = D[n_-2+i]
        new = D[n_-2+i+l]

        #print(':', old, new, end=' ')

        if m >= new:
            m = new

        if m == old:
            m = findMin(i, i+l)

        print('', m, end='')

        #print(findMin(i, i+l))
    print()

Submission status: Time Limit Exceeded

Solution code:
# Sliding Minimum Elements
INF = 2**31 - 1
D = [INF]
[n, l] = list(map(int, input().split()))
data = list(map(int, input().split()))


def initRMQ(data):
    global D, n
    size = 1
    while size < l:
        size *= 2
    i = 1
    while i <= 2*size - 1 - 1:
        D.append(INF)
        i += 1
    n = size
    
    k = n - 1
    D[k:k+len(data)] = data
    start = k
    #print(start)
    while start > 0:
        i = int((start - 1)/2)
        while i < start:
            D[i] = min(D[i*2 + 1], D[i*2 + 2])
            i += 1
        start = int((start - 1)/2)
    
def update(k, a):
    global n
    k += n - 1
    D[k] = a
    while k > 0:
        k = int((k - 1)/2)
        D[k] = min(D[k*2 + 1], D[k*2 + 2])

"""
def update(k, data):
    global D
    k += n - 1
    D[k:k+len(data)] = data
    for i in range(k, k+len(data), 2):
        while i > 0:
            i = int((i - 1)/2)
            D[i] = min(D[i*2 + 1], D[i*2 + 2])
"""
"""
def update(k, data):
    global D
    k += n - 1
    #D[k:k+len(data)] = data
    D[k:k+len(data)] = data
    start = k
    while start > 0:
        i = int((start - 1)/2)
        while i < start:
            D[i] = min(D[i*2 + 1], D[i*2 + 2])
            i += 1
        start = int((start - 1)/2)
"""

def query(a, b, k, l, r):
    global INF, D
    if r <= a or b <= l:
        return INF
    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((l + r)/2))
    vr = query(a, b, k*2 + 2, int((l + r)/2), r)
    return min(vl, vr)

def findMin(a, b):
    global n
    return query(a, b + 1, 0, 0, n)


index = 0
initRMQ(data[index:index+l])
#print(0, "", end="")
#print(D)
#update(0, data[index:index+l])
#update(0, data)

time = 0
while (len(data) - index - l) >= 0:
    time += 1
    #update(0, data[index:index+l])
    if (len(data) - (index + 1) - l) >= 0:
        #print(time)
        print(D[0], "", end="")
        update(index%l, data[index+l])
        #print(D)
    else:
        #print(time)
        print(D[0])
    index += 1

Submission status: Accepted

Solution code:
import collections, numbers
import random

def compute(array, window, maximize):
    if not isinstance(window, numbers.Integral):
        raise TypeError()
    if not isinstance(maximize, bool):
        raise TypeError()
    if window <= 0:
        raise ValueError("Window size must be positive")

    result = []
    deque = collections.deque()
    for i, val in enumerate(array):
        val = array[i]
        while len(deque) > 0 and ((not maximize and val < deque[-1]) or (maximize and val > deque[-1])):
            deque.pop()
        deque.append(val)

        j = i + 1 - window
        if j >= 0:
            result.append(deque[0])
            if array[j] == deque[0]:
                deque.popleft()
    return result


class SlidingWindowMinMax(object):

    def __init__(self):
        self.mindeque = collections.deque()
        self.maxdeque = collections.deque()

    def get_minimum(self):
        return self.mindeque[0]

    def get_maximum(self):
        return self.maxdeque[0]

    def add_tail(self, val):
        while len(self.mindeque) > 0 and val < self.mindeque[-1]:
            self.mindeque.pop()
        self.mindeque.append(val)

        while len(self.maxdeque) > 0 and val > self.maxdeque[-1]:
            self.maxdeque.pop()
        self.maxdeque.append(val)

    def remove_head(self, val):
        if val < self.mindeque[0]:
            raise ValueError("Wrong value")
        elif val == self.mindeque[0]:
            self.mindeque.popleft()

        if val > self.maxdeque[0]:
            raise ValueError("Wrong value")
        elif val == self.maxdeque[0]:
            self.maxdeque.popleft()

if __name__ == "__main__":
    n, l = (int(x) for x in input().split())
    array = list((int(x) for x in input().split()))

    answer = compute(array, l, False)
    print(*answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N,L = list(map(int, input().split()))
alist = list(map(int, input().split()))
arr = []
for i in range(L):
  while arr and alist[i] <= alist[arr[-1]]:
    arr.pop()
  arr.append(i)
for i in range(L, N):
  print(alist[arr[0]], end=' ')
  while arr and arr[0] <= i-L:
    arr.pop(0)
  while arr and alist[i] <= alist[arr[-1]]:
    arr.pop()
  arr.append(i)
print(alist[arr[0]])

Submission status: Accepted

Solution code:
import collections, numbers
import random

def compute(array, window, maximize):
    if not isinstance(window, numbers.Integral):
        raise TypeError()
    if not isinstance(maximize, bool):
        raise TypeError()
    if window <= 0:
        raise ValueError("Window size must be positive")

    result = []
    deque = collections.deque()
    for i, val in enumerate(array):
        val = array[i]
        while len(deque) > 0 and ((not maximize and val < deque[-1]) or (maximize and val > deque[-1])):
            deque.pop()
        deque.append(val)

        j = i + 1 - window
        if j >= 0:
            result.append(deque[0])
            if array[j] == deque[0]:
                deque.popleft()
    return result


if __name__ == "__main__":
    n, l = (int(x) for x in input().split())
    array = list((int(x) for x in input().split()))

    answer = compute(array, l, False)
    print(*answer)

Submission status: Accepted

Solution code:
INTMAX = (1<<31) - 1

def ans():
    for i in range(k):
        x = i + OFS
        A[x] = arr[i]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r#min(tree[left],tree[right])
    res = []
    c = 0
    for i in range(_N-k):
        res.append(A[0])
        x = c + OFS
        A[x] = arr[i+k]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r
        c += 1
        if(c == k):
            c = 0
    res.append(A[0])
    print(*res)

_N,k = map(int, input().split())
*arr, = map(int,input().split())
if(k==1):
    print(*arr)
else:
    N = 2**(_N-1).bit_length()
    A = [INTMAX]*(2*N)
    OFS = N - 1
    ans()

Submission status: Accepted

Solution code:
def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini :
            mini = A[i+L-1]
        elif A[i-1] == mini :
            mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini :
            mini = A[i]
        elif A[i+L] == mini:
            mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)

Pcount = 0;
Mcount = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : Pcount += 1
        if A[i+1] < A[i] : Mcount += 1
    if Pcount > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Accepted

Solution code:
def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Accepted

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

ans = []
q = deque()

for i, a in enumerate(A):
    while q and A[q[-1]] >= a:
        q.pop()
    q.append(i)
    if i - L + 1 >= 0:
        ans.append(A[q[0]])
        if q[0] == i - L + 1:
            q.popleft()

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

N, L = map(int, input().split())
*A, = map(int, input().split())

ans = []

que = deque()
for i, a in enumerate(A):
    while que and a <= que[-1][1]:
        que.pop()
    que.append((i, a))

    ans.append(que[0][1])

    if que and que[0][0] <= i+1-L:
        que.popleft()

print(*ans[L-1:])

Submission status: Accepted

Solution code:
import collections

#  copyright by: Weizheng Wang
def sme():
    for cur, M in enumerate(element):
        while que and M <= que[-1][1]:  # 如果插入的元素小于队列最后一个元素，则弹出当前队列元素，保证队列第一个元素是最小值
            que.pop()
        que.append((cur, M))  # 队列压入数组元素的序号和内容(0,1)

        res.append(que[0][1])  # 队列压入数组元素内容[1]

        if que and que[0][0] == cur - L + 1:  # 如果队列队首元素和当前元素的距离等于L时，则弹出队首元素 队首压入新元素就变成旧元素
            que.popleft()


N, L = map(int, input().split())  # N数组元素个数 L数组长度
element = list(map(int, input().split()))  # element数组
que = collections.deque()  # 双向队列
res = []  # 结果数组
sme()
print(*res[L - 1:])  # 输出结果

Submission status: Accepted

Solution code:
from collections import deque

N, L = map(int, input().split())
*list, = map(int, input().split())

ans = []

que = deque()
for i, num in enumerate(list):
    while que and num <= que[-1][1]:
        que.pop()
    que.append((i, num))

    ans.append(que[0][1])

    if que and que[0][0] <= i+1-L:
        que.popleft()

print(*ans[L-1:])

Submission status: Accepted

Solution code:
from collections import deque
ans = []

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

que = deque()
for i, a in enumerate(A):
    while que and a <= que[-1][1]:
        que.pop()
    que.append((i,a))

    ans.append(que[0][1])

    if que and que[0][0] <= i+1-L:
        que.popleft()
    
ans = ans[L-1:]
print(*ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import deque
class SWAG:
    def __init__(self, operator_M, e_M):
        self.op_M = operator_M
        self.e_M = e_M
        self.q = deque([])
        self.accL = []
        self.accR = e_M
        self.L = self.R = 0

    def build(self,lst):
        self.q = deque(lst)
        self.L = len(lst)
        self.accL = list(accumulate(reversed(self.q),self.op_M))

    def __len__(self):
        return self.L + self.R

    def fold_all(self):
        if self.L: return self.op_M(self.accL[-1],self.accR)
        else: return self.accR

    def append(self,x):
        self.q.append(x)
        self.accR = self.op_M(self.accR,x)
        self.R += 1
    
    def popleft(self):
        if self.L:
            self.accL.pop()
            self.L -= 1
            return self.q.popleft()
        elif self.R:
            self.L,self.R = self.R-1,0
            self.accL = list(accumulate(reversed(self.q),self.op_M))
            self.accR = self.e_M
            self.accL.pop()
            return self.q.popleft()
        else:
            assert 0


# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,l,*a = [int(i) for i in read().split()]

q = SWAG(min,10**9)
q.build(a[:l])
ans = [q.fold_all()]
for i in a[l:]:
    q.popleft()
    q.append(i)
    ans.append(q.fold_all())

print(*ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

class SlidingWindowAggretgation:
    def __init__(self, default = float("inf"), f = min):
        self.default = default
        self.f = f
        self.front_stack = deque()
        self.back_stack = deque()

    def get(self):
        res = self.default
        if self.front_stack:
            res = self.f(res, self.front_stack[-1][1])
        if self.back_stack:
            res = self.f(res, self.back_stack[-1][1])
        return res

    def append(self, x):
        fx = x
        if self.back_stack:
            fx = self.f(self.back_stack[-1][1], x)
        self.back_stack.append((x, fx))

    def popleft(self):
        if not self.front_stack:
            x, fx = self.back_stack.pop()
            self.front_stack.append((x, x))
            while self.back_stack:
                x, fx = self.back_stack.pop()
                fx = self.f(x, self.front_stack[-1][1])
                self.front_stack.append((x, fx))
        self.front_stack.pop()

def solve():
    n,l = LI()
    a = LI()
    swag = SlidingWindowAggretgation()
    ans = []
    for i in range(n):
        swag.append(a[i])
        if i+1 >= l:
            ans.append(swag.get())
            swag.popleft()
    print(*ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class SWAG:
  def __init__(self,func,ide):
    self.ide = ide
    self.func = func
    self.front = []
    self.back = []
  
  def push(self,x):
    # 累積の結果を残す
    if self.back: y = self.func(self.back[-1][1],x)
    else: y = x
    self.back.append((x,y))
  
  def pop(self):
    if not self.front:
      while self.back:
        x,y = self.back.pop()
        if self.front: y = self.func(self.front[-1][1],x)
        else: y = x
        self.front.append((x,y))
    return self.front.pop()[1]
  
  def fold_all(self):
    y = self.ide
    if self.front: y = self.func(self.front[-1][1],y)
    if self.back: y = self.func(self.back[-1][1],y)
    return y
ans = []
n,l = map(int,input().split())
data = list(map(int,input().split()))
swag = SWAG(min,inf)
for i in range(l-1):
  swag.push(data[i])
for i in range(l-1,n):
  swag.push(data[i])
  ans.append(swag.fold_all())
  swag.pop()
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

def slide_min(L:int, li:list):
	deq=deque()
	ret=[]
	for i,x in enumerate(li):
		while deq and deq[-1][1]>x:
			deq.pop()
		deq.append((i,x))
		if deq[0][0]+L==i:
			deq.popleft()
		ret.append(deq[0][1])
	return ret[L-1:]

def main():
	n,l,*a=map(int,open(0).read().split())
	print(*slide_min(l,a))

if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class SWAG(object):
    def __init__(self,dot):
        self.__front=[]
        self.__back=[]
        self.__dot=dot

    def __bool__(self):
        return True if(self.__front or self.__back) else False

    def __len__(self):
        return len(self.__front)+len(self.__back)

    def sum(self):
        assert(self)
        front=self.__front; back=self.__back
        if(not front): return back[-1][1]
        elif(not back): return front[-1][1]
        else: return self.__dot(front[-1][1],back[-1][1])

    def append(self,x):
        back=self.__back
        if(not back): back.append((x,x))
        else: back.append((x,self.__dot(back[-1][1],x)))

    def popleft(self):
        assert(self)
        front=self.__front; back=self.__back
        if(not front):
            front.append((back[-1][0],back[-1][0]))
            back.pop()
            while(back):
                front.append((back[-1][0],self.__dot(back[-1][0],front[-1][1])))
                back.pop()
        front.pop()

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    ans=[None]*n
    swag=SWAG(min)
    for i,a in enumerate(A):
        swag.append(a)
        ans[i]=swag.sum()
        if(i-k+1>=0): swag.popleft()
    print(*ans[k-1:])
resolve()

Submission status: Accepted

Solution code:
from collections import deque


if __name__ == "__main__":
    N, L = map(int, input().split())
    a = list(map(lambda x: int(x), input().split()))

    que: deque = deque()
    ans = []
    for i, elem in enumerate(a):
        while (que and elem <= que[-1][1]):
            que.pop()
        que.append((i, elem))

        ans.append(que[0][1])

        if (que and que[0][0] <= i + 1 - L):
            que.popleft()

    print(" ".join([str(elem) for elem in ans[L - 1:]]))

Submission status: Accepted

Solution code:
def ascend(x,y):
    mini = min(A[x:x+L])
    ans[x] = mini
    for i in range(x+1,y):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini
 
def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
     
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Accepted

Solution code:
import collections

N, L = map(int, input().split())
a = list(map(int, input().split()))
deq = collections.deque()
ans = []

for i in range(N):
    while deq and a[i] <= deq[-1][1]:deq.pop()
    deq.append((i,a[i]))
    ans.append(deq[0][1])
    if deq and deq[0][0] <=i-L+1:deq.popleft()
print(*ans[L-1:N])

Submission status: Accepted

Solution code:
import sys


def get_sliding_minimum_element(nums, k):
    res = []
    queue = []
    for i, v in enumerate(nums):
        if queue and queue[0] <= i - k:
            queue = queue[1:]
        while queue and nums[queue[-1]] > v:
            queue.pop()
        queue.append(i)
        if i + 1 >= k:
            res.append(nums[queue[0]])
    return res


b = [0 for _ in range(1000000)]
deq = [0 for _ in range(1000000)]

line = sys.stdin.readline()
n, l = map(int, line.split())
arr = list(map(int, input().split()))
s = 0
t = 0
for i in range(n):
    while s < t and arr[deq[t - 1]] >= arr[i]:
        t -= 1
    deq[t] = i
    t += 1
    if i - l + 1 >= 0:
        b[i - l + 1] = arr[deq[s]]
        if deq[s] == i - l + 1:
            s += 1

for i in range(n-l+1):
    if i == n - l:
        print(str(b[i]), end='')
    else:
        print(str(b[i]) + " ", end='')
print("\n", end='')

Submission status: Accepted

Solution code:
from collections import deque

N, L = map(int, input().split())
box = list(map(int, input().split()))

que = deque()
ans = []
for i, a in enumerate(box):
    while que and a <= que[-1][1]:
        que.pop()
    que.append((i,a))
    
    ans.append(que[0][1])
    if que and que[0][0] <= i-L+1:
        que.popleft()
        
print(*ans[L-1:])

Submission status: Accepted

Solution code:
from collections import deque

N, L = map(int, input().split())
*A, = map(int, input().split())

ans = []

que = deque()
for i, a in enumerate(A):
    while que and a <= que[-1][1]:
        que.pop()
    que.append((i, a))

    ans.append(que[0][1])

    if que and que[0][0] <= i+1-L:
        que.popleft()

print(*ans[L-1:])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DSL_3_D: Sliding Minimum Elements
# heapq and lazy delete

from heapq import heappush, heappop


def run():
    _, size = [int(x) for x in input().split()]
    heap = []
    removed = set()
    result = []
    n = 0
    for i, v in enumerate(input().split()):
        heappush(heap, (int(v), i))
        n += 1
        if n > size:
            removed.add(i - size)
            n -= 1

        if n == size:
            while len(heap) > 0:
                minv, k = heap[0]
                if k in removed:
                    removed.remove(k)
                    heappop(heap)
                else:
                    result.append(str(minv))
                    break
    print(" ".join(result))


if __name__ == '__main__':
    run()

Submission status: Runtime Error

Solution code:
answer=[]
element=[]
D=[]
def initRMQ(nn):
    global n
    n = 1
    while n < nn:
        n*=2
    for i in range(2*n-1):
        D.append(2147483647)

def update(k,a):
    k += n-1
    D[k] = a
    while k>0:
        k = (k-1)//2
        D[k] = min(D[k*2+1] , D[k*2+2])
        
def findMin(a,b):
    return query(a,b,0,0,n)

def query(a,b,k,l,r):
    if r <= a or b <= l:
        return 2147483647
    if a <= l and r <= b:
        return D[k]
    
    vl = query(a, b, (k*2)+1, l, (l+r)//2)
    vr = query(a, b, (k*2)+2, (l+r)//2, r)
    return min(vl,vr)


N,L = map(int,input().split())
initRMQ(N)
element = input().split()
for i in range(len(element)):
    update(i,int(element[i]))
for i in range(N-L+1):
    answer.append(findMin(i,i+L))

for i in range(len(answer)):
    print(answer[i],end='')
    x+=1
    if x == len(answer):
        print('',end='\n')
        break
    print(' ',end='')

Submission status: Runtime Error

Solution code:
def binaryinsertion(A,x):
    left=0;right=len(A)-1;centre = len(A)//2
    while(True):
        if(left == right):
            if(x[0]<A[left][0]):
                A.insert(left,x)
                break
            else :
                A.insert(left+1,x)
                break
        else:
            if(x[0] < A[centre][0]) :
                right = centre - 1
            elif(A[centre][0] < x[0]) :
                left = centre + 1
            else : 
                A.insert(centre,x)
                break
            centre = left + (right-left + 1)//2

[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
sweep = A[:L]
sweep = sorted(sweep)
ans = [str(sweep[0][0])]
for i in range(L,N) :
    sweep.remove(A[i-L])
    binaryinsertion(sweep,A[i])
    ans.append(str(sweep[0][0]))
print(" ".join(ans))

Submission status: Runtime Error

Solution code:
def binaryinsertion(A,x):
    left=0;right=len(A)-1;centre = len(A)//2
    while(True):
        if(left == right):
            if(x[0]<A[left][0]):
                A.insert(left,x)
                break
            else :
                A.insert(left+1,x)
                break
        else:
            if(x[0] < A[centre][0]) :
                right = centre - 1
            elif(A[centre][0] < x[0]) :
                left = centre + 1
            else : 
                A.insert(centre,x)
                break
            centre = left + (right-left+1)//2

[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
sweep = A[:L]
sweep = sorted(sweep)
ans = [str(sweep[0][0])]
for i in range(L,N) :
    sweep.remove(A[i-L])
    binaryinsertion(sweep,A[i])
    ans.append(str(sweep[0][0]))
print(" ".join(ans))