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:
import sys
input = sys.stdin.readline
import math
sys.setrecursionlimit(20000)
def update(tree,x,y,N):
    # offset
    #x += int(N/2)
    x += N - 1
    tree[x] = y
    # segment tree no update suru
    while True:
        if(x <= 0):
            break
        x = math.floor((x - 1)/2)
        left = x*2+1
        right = x*2+2
        tree[x] = min(tree[left],tree[right])

def find(tree,x,y,k,l,r):

    if (r <= x or y <= l):
        return 2**31 - 1
    # sita wo mite itte mitukatta toki (intersect)
    if ( x <= l and r <= y):
        return tree[k]
    # sita ni sagaru
    v_left = find(tree, x, y, k*2 + 1, l, int((l+r)/2))
    v_right = find(tree, x, y, k*2 + 2, int((l+r)/2), r)
    return min(v_left, v_right)

if __name__ == '__main__':
    _N,k = map(int, input().split())
    arr = list(map(int,input().split()))
    INT_MAX = 2**31 - 1
    N = 1
    res = []
    while True:
        if(N >= _N):
            break
        N *= 2
    #N = 2*N - 1 - 1
    if not (N == 1):
        A_bin_tree = [INT_MAX]*(2*N - 1)
    else:
        A_bin_tree = [INT_MAX]
    for i in range(_N):
        update(A_bin_tree,i,arr[i],N)

    for i in range(_N-k+1):
        z = find(A_bin_tree,i,i+k,0,0,N)
        res.append(z)

    print(" ".join([str(r) for r in res]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
sys.setrecursionlimit(20000)
INT_MAX = 2**31 - 1
def update(tree,x,y,N):
    # offset
    #x += int(N/2)
    x += N - 1
    tree[x] = y
    # segment tree no update suru
    while True:
        if(x <= 0):
            break
        x = math.floor((x - 1)/2)
        left = x*2+1
        right = x*2+2
        tree[x] = min(tree[left],tree[right])

def find(tree,x,y,k,l,r):

    if (r <= x or y <= l):
        return INT_MAX - 1
    # sita wo mite itte mitukatta toki (intersect)
    if ( x <= l and r <= y):
        return tree[k]
    # sita ni sagaru
    v_left = find(tree, x, y, k*2 + 1, l, int((l+r)/2))
    v_right = find(tree, x, y, k*2 + 2, int((l+r)/2), r)
    return min(v_left, v_right)

if __name__ == '__main__':
    _N,k = map(int, input().split())
    arr = list(map(int,input().split()))
    N = 1
    res = []
    while True:
        if(N >= _N):
            break
        N *= 2
    #N = 2*N - 1 - 1
    if not (N == 1):
        A_bin_tree = [INT_MAX]*(2*N - 1)
    else:
        A_bin_tree = [INT_MAX]
    for i in range(k):
        update(A_bin_tree,i,arr[i],N)

    for i in range(_N-k):
        res.append(find(A_bin_tree,i,i+k,0,0,N))
        update(A_bin_tree,i+k,arr[i+k],N)

    res.append(find(A_bin_tree,_N-k,_N,0,0,N))
    print(" ".join([str(r) for r in res]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from random import shuffle
input = sys.stdin.readline

def left_rot(node):
    s = node['right'].copy()
    node['right'] = s['left']#.copy()
    s['left'] = node
    return s

def right_rot(node):
    s = node['left'].copy()
    node['left'] = s['right']#.copy()
    s['right'] = node
    return s

def insert(node,k,p):
    if(node is None):
        child = {
            'left' : None,
            'right' : None,
            'key' : k,
            'priority' : p}
        return child
    if(k == node['key']):
        return node
    # Left side
    if(k < node['key']):
        node['left'] = insert(node['left'],k,p)
        #追加したらあとは優先度による回転を行う
        if(node['priority'] < node['left']['priority']):
            node = right_rot(node)
    # Right side
    else:
        node['right'] = insert(node['right'],k,p)
        #追加したらあとは以下略
        if(node['priority'] < node['right']['priority']):
            node = left_rot(node)

    return node

def find(node,k):
    if(node is None):
        return k
    if(node['key'][0] < k):
        k = node['key'][0]
    min_left = find(node['left'],k)
    min_right = find(node['right'],k)
    return min(min_left,min_right)

def delete(node, k):
    if(node is None):
        return None

    if(node['key'] == k):
        if(node['left'] is None and node['right'] is None):
            return None
        elif(node['left'] is None):
            node = left_rot(node)
        elif(node['right'] is None):
            node = right_rot(node)
        else:
            if(node['left']['priority'] > node['right']['priority']):
                node = right_rot(node)
            else:
                node = left_rot(node)
        return delete(node, k)
    if(k < node['key']):
        node['left'] = delete(node['left'], k)
    else:
        node['right'] = delete(node['right'], k)

    return node

N,k = map(int, input().split())
*arr, = map(int,input().split())
node = None
priorities = list(range(N))
shuffle(priorities)
for i in range(k):
    #p = priorities.pop(0)
    node = insert(node, (arr[i],i), priorities[i])
    #priorities.append(p)
ans = []
INT_MAX = 10**9
for i in range(N-k):
    ans.append(find(node,INT_MAX))
    #p = priorities.pop(0)
    node = delete(node, (arr[i],i))
    node = insert(node, (arr[i+k],i+k), priorities[i+k])
    #priorities.append(p)

ans.append(find(node,INT_MAX))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
INT_MAX = 2**31 - 1
def update(tree,x,y,N):
    x += N - 1
    tree[x] = y
    while True:
        if(x <= 0):
            break
        x = math.floor((x - 1)/2)
        left = x*2+1
        right = x*2+2
        tree[x] = min(tree[left],tree[right])

def find(tree,x,y,k,l,r):

    if (r <= x or y <= l):
        return INT_MAX - 1
    if ( x <= l and r <= y):
        return tree[k]
    v_left = find(tree, x, y, k*2 + 1, l, int((l+r)/2))
    v_right = find(tree, x, y, k*2 + 2, int((l+r)/2), r)
    return min(v_left, v_right)

_N,k = map(int, input().split())
*arr, = map(int,input().split())
N = 1
res = []
while True:
    if(N >= _N):
        break
    N *= 2
if not (N == 1):
    A_bin_tree = [INT_MAX]*(2*N - 1)
else:
    A_bin_tree = [INT_MAX]
for i in range(_N):
    update(A_bin_tree,i,arr[i],N)

for i in range(_N-k+1):
    z = find(A_bin_tree,i,i+k,0,0,N)
    res.append(z)

print(*res)

Submission status: Time Limit Exceeded

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


line = sys.stdin.readline()
n, l = map(int, line.split())
arr = list(map(int, input().split()))
res = get_sliding_minimum_element(arr, l)
print(' '.join(map(str, res)))

Submission status: Time Limit Exceeded

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

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

MIN = 0
for i in range(N-L+1):
  MIN = alist[i]
  for j in range(1, L):
    if alist[i+j] < MIN:
      MIN = alist[i+j]
  if i != N-L:
    print(MIN, end=' ')
  else:
    print(MIN)

Submission status: Time Limit Exceeded

Solution code:
INT_MAX = 2**31 - 1
def update():
    for i in range(_N):
        x = i + N - 1
        A_bin_tree[x] = arr[i]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            left = x*2+1
            right = x*2+2
            A_bin_tree[x] = min(A_bin_tree[left],A_bin_tree[right])

def find(x,y,k,l,r):

    if (r <= x or y <= l):
        return INT_MAX
    if ( x <= l and r <= y):
        return A_bin_tree[k]
    v_left = find(x, y, k*2 + 1, l, int((l+r)/2))
    v_right = find(x, y, k*2 + 2, int((l+r)/2), r)
    return min(v_left, v_right)

_N,k = map(int, input().split())
*arr, = map(int,input().split())
N = 1
res = []
while True:
    if(N >= _N):
        break
    N *= 2
if not (N == 1):
    A_bin_tree = [INT_MAX]*(2*N - 1)
else:
    A_bin_tree = [INT_MAX]
update()

for i in range(_N-k+1):
    z = find(i,i+k,0,0,N)
    res.append(z)

print(*res)

Submission status: Time Limit Exceeded

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

def update():
    for i in range(_N):
        x = i+N-1
        A_bin_tree[x] = arr[i]
        while x > 1:
            x >>= 1
            l, r = A_bin_tree[x<<1], A_bin_tree[(x<<1)+1]
            A_bin_tree[x] = min(l,r)#l if l < r else r

def find(x,y):
    l = x+N-1
    r = y+N-1
    z = INT_MAX
    while l < r:
        if l & 1:
            if(A_bin_tree[l] < z):
                z = A_bin_tree[l]
            l += 1
        if r & 1:
            r -= 1
            if(A_bin_tree[r] < z):
                z = A_bin_tree[r]
        l >>= 1
        r >>= 1
    return z

import sys
input = sys.stdin.readline
_N,k = map(int,input().split())
*arr, = map(int,input().split())
N = 1
while True:
    if(N >= _N):
        break
    N = N << 1
A_bin_tree = [INT_MAX]*(2*N)

update()
res = [find(i,i+k) for i in range(_N-k+1)]
print(*res)

Submission status: Time Limit Exceeded

Solution code:
INT_MAX = (1<<31) - 1
def update():
    for i in range(_N):
        x = i+N-1
        A_bin_tree[x] = arr[i]
        while x > 1:
            x >>= 1
            y = x<<1
            l = A_bin_tree[y]
            r = A_bin_tree[y+1]
            A_bin_tree[x] = l if l < r else r#min(l,r)

def find(x,y):
    l = x+N-1
    r = y+N-1
    z = INT_MAX
    while l < r:
        if l & 1:
            if(A_bin_tree[l] < z):
                z = A_bin_tree[l]
            l += 1
        if r & 1:
            r -= 1
            if(A_bin_tree[r] < z):
                z = A_bin_tree[r]
        l >>= 1
        r >>= 1
    return z

import sys
input = sys.stdin.readline
_N,k = map(int,input().split())
*arr, = map(int,input().split())
N = 1
N = 2**(_N-1).bit_length()
A_bin_tree = [INT_MAX]*(N<<1)
update()
res = [find(i,i+k) for i in range(_N-k+1)]
print(*res)

Submission status: Time Limit Exceeded

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

def update():
    for i in range(_N):
        x = i+N-1
        A[x] = arr[i]
        while x > 1:
            x >>= 1
            y = x<<1
            l = A[y]
            r = A[y+1]
            A[x] = l if l < r else r#min(l,r)

def find():
    res = [0]*(_N-k+1)
    for i in range(_N-k+1):
        l = i+N-1
        r = i+k+N-1
        z = INTMAX
        while l < r:
            if l & 1:
                if(A[l] < z):
                    z = A[l]
                l += 1
            if r & 1:
                r -= 1
                if(A[r] < z):
                    z = A[r]
            l >>= 1
            r >>= 1
        res[i] = z
    print(*res)

_N,k = map(int,input().split())
*arr, = map(int,input().split())
N = 1
N = 2**(_N-1).bit_length()
A = [INTMAX]*(N<<1)
update()
find()

Submission status: Time Limit Exceeded

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

def ans():
    for i in range(_N):
        x = i+OFS#N-1
        A[x] = arr[i]
        while x > 1:
            x >>= 1
            y = x<<1
            l = A[y]
            r = A[y+1]
            A[x] = l if l < r else r#min(l,r)

    res = [0]*(_N-k+1)
    for i in range(_N-k+1):
        l = i+OFS#N-1
        r = i+k+OFS#N-1
        z = INTMAX
        while l < r:
            if l & 1:
                p = A[l]
                z = p if p < z else z
                l += 1
            if r & 1:
                r -= 1
                p = A[r]
                z = p if p < z else z
            l >>= 1
            r >>= 1
        res[i] = z
    print(*res)

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

Submission status: Time Limit Exceeded

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))
x=0
for i in range(len(answer)):
    print(answer[i],end='')
    x+=1
    if x == len(answer):
        print('',end='\n')
        break
    print(' ',end='')

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = ""
for i in range(N-L+1):
    ans += str(min(A[i:i+L])) + " "
print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = ""
for i in range(N-L+1) : ans += str(min(A[i:i+L])) + " "
print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
for i in range(N-L+1) : ans.append(str(min(A[i:i+L])))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import heapq

def h(l):
    heapq.heapify(l)
    return l[0]

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
for i in range(N-L+1) : ans.append(str(h(A[i:i+L])))
print(" ".join(ans))

Submission status: Time Limit Exceeded

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
            else : 
                A.insert(centre,x)
                break
            centre = left + (right-left)//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: Time Limit Exceeded

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

Solution code:
import math

def binaryinsertion(A,x):
    left=0;right=len(A)-1
    while(True):
        centre = math.floor((left + right) / 2)
        if(right == left):
            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

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

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

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

Solution code:
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
        
def search_min(node):
    while node.left is not None:
        node = node.left
    return node.data

def insert(node, x):
    if node is None : return Node(x)
    elif x < node.data :
        node.left = insert(node.left, x)
    else :
        node.right = insert(node.right, x)
    return node

def delete_min(node):
    if node.left is None : return node.right
    node.left = delete_min(node.left)
    return node

def delete(node, x):
    if node is not None :
        if x == node.data :
            if node.left is None :
                return node.right
            elif node.right is None:
                return node.left
            else :
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data :
            node.left = delete(node.left, x)
        else :
            node.right = delete(node.right, x)
    return node

[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
Tree = None
for i in range(L) : Tree = insert(Tree,A[i])
ANS = [str(search_min(Tree)[0])]

for i in range(L,N):
    Tree = delete(Tree, A[i-L])
    Tree = insert(Tree, A[i])
    ANS.append(str(search_min(Tree)[0]))
    
print(" ".join(ANS))

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
A = sorted(A)
ANS = [10**9+1]*N
for a in A:
    for i in range(L):
        try :
            if a[0] < int(ANS[a[1]+i]) :
                ANS[a[1]+i] = str(a[0])
        except IndexError : continue
print(" ".join(ANS[L-1:]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
heapq.heapify(A)
ANS = [10**9+1]*N
for j in range(N):
    a = heapq.heappop(A)
    for i in range(L):
        try :
            if a[0] < int(ANS[a[1]+i]) : ANS[a[1]+i] = str(a[0])
        except IndexError : continue
print(" ".join(ANS[L-1:]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
[N,L] = [int(x) for x in input().split()]
A = [(int(x),int(i)) for i,x in enumerate(input().split())]
heapq.heapify(A)
ANS = [10**9+1]*N
for j in range(N):
    a = heapq.heappop(A)
    for i in range(L):
        try :
            if a[0] < int(ANS[a[1]+i]) : ANS[a[1]+i] = str(a[0])
        except IndexError : continue
print(" ".join(ANS[L-1:]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
heapq.heapify(A)
ANS = [10**9+1]*N
for j in range(N):
    a = heapq.heappop(A)
    for i in range(L):
        try :
            if ANS[a[1]+i] == 10**9+1 : ANS[a[1]+i] = str(a[0])
        except IndexError : continue
print(" ".join(ANS[L-1:]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
heapq.heapify(A)
ANS = [10**9+1]*N
for j in range(N):
    a = heapq.heappop(A)
    for i in range(L):
        try :
            if ANS[a[1]+i] == 10**9+1 : ANS[a[1]+i] = a[0]
        except IndexError : continue
for i in ANS[L-1:-1]:
    print(i, end=" ")
print(ANS[-1])

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
        
def search_min(node):
    while node.left is not None:
        node = node.left
    return node.data

def insert(node, x):
    if node is None : return Node(x)
    elif x < node.data :
        node.left = insert(node.left, x)
    else :
        node.right = insert(node.right, x)
    return node

def delete_min(node):
    if node.left is None : return node.right
    node.left = delete_min(node.left)
    return node

def delete(node, x):
    if node is not None :
        if x == node.data :
            if node.left is None :
                return node.right
            elif node.right is None:
                return node.left
            else :
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data :
            node.left = delete(node.left, x)
        else :
            node.right = delete(node.right, x)
    return node

[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
Tree = None
for i in range(L) : Tree = insert(Tree,A[i])
ANS = [search_min(Tree)[0]]

for i in range(L,N):
    Tree = delete(Tree, A[i-L])
    Tree = insert(Tree, A[i])
    ANS.append(search_min(Tree)[0])
    
for i in ANS[:-1]:
    print(i, end=" ")
print(ANS[-1])

Submission status: Time Limit Exceeded

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

[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 = [sweep[0][0]]
for i in range(L,N) :
    sweep.remove(A[i-L])
    binaryinsertion(sweep,A[i])
    ans.append(sweep[0][0])
for i in ans[:-1]:
    print(i, end=" ")
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
for i in range(N-L+1) : ans.append(min(A[i:i+L]))
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq
[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
heapq.heapify(A)
ANS = [10**9+1]*N
count = 0
for j in range(N):
    a = heapq.heappop(A)
    for i in range(L):
        try :
            if ANS[a[1]+i] == 10**9+1 :
                ANS[a[1]+i] = str(a[0])
                count += 1
        except IndexError : continue
    if count == N : break
print(" ".join(ANS[L-1:]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
heapq.heapify(A)
ANS = [10**9+1]*N
count = 0
for j in range(N):
    a = heapq.heappop(A)
    for i in range(L):
        try :
            if ANS[a[1]+i] == 10**9+1 :
                ANS[a[1]+i] = a[0]
                count += 1
        except IndexError : continue
    if count == N : break
for i in ANS[L-1:-1]:
    print(i, end=" ")
print(ANS[-1])

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = {}
ANS = [10**9+1]*N
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]

for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            try :
                if ANS[j+k] == 10**9+1 : 
                    ANS[j+k] = i
                    count += 1
            except IndexError : continue
    if count == N : break
for i in ANS[L-1:-1] : print(i, end=" ")
print(ANS[-1])

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = {}
ANS = [10**9+1]*N
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]

for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            try :
                if ANS[j+k] == 10**9+1 : 
                    ANS[j+k] = i
                    count += 1
            except IndexError : continue
            if count == N : break
for i in ANS[L-1:-1] : print(i, end=" ")
print(ANS[-1])

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = {}
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count > N + 100 : break
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = {}
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = {}
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count > N + L : break

for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = {}
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count > N + 200 : break

for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = {}
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS and j + k < N:
                ANS[j+k] = i
                count += 1
    if count == N : break

for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = {}
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k in ANS :
                continue
            elif j + k < N :
                ANS[j+k] = i
                count += 1
    if count == N : break

for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq
[N,L] = [int(x) for x in input().split()]
A = []
for i,x in enumerate(input().split()):
    heapq.heappush(A,[int(x),int(i)])
heapq.heapify(A)
ANS = [10**9+1]*N
count = 0
for j in range(N):
    a = heapq.heappop(A)
    for i in range(L):
        try :
            if ANS[a[1]+i] == 10**9+1 :
                ANS[a[1]+i] = str(a[0])
                count += 1
        except IndexError : continue
    if count == N : break
print(" ".join(ANS[L-1:]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
[N,L] = [int(x) for x in input().split()]
A = []
for i,x in enumerate(input().split()):
    heapq.heappush(A,[int(x),int(i)])
heapq.heapify(A)
ANS = [10**9+1]*N
count = 0
for j in range(N):
    a = heapq.heappop(A)
    for i in range(L):
        try :
            if ANS[a[1]+i] == 10**9+1 :
                ANS[a[1]+i] = a[0]
                count += 1
        except IndexError : continue
    if count == N : break
for i in ANS[L-1:-1] : print(i, end=" ")
print(ANS[-1])

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = {}
B = [True]*N
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if (N-count)**2 < N : break

for i in range(L):
    if i not in ANS:
        ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS:
            ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

Submission status: Time Limit Exceeded

Solution code:
[N,L] = [int(x) for x in input().split()]
A = {}
B = []
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B.append(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if (N-count)**2 < N : break

for i in range(L):
    if i not in ANS : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])