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: Wrong Answer

Solution code:
import sys
import time
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
    # 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'] < k):
        k = node['key']
    min_left = find(node['left'],k)
    min_right = find(node['right'],k)
    return min(min_left,min_right)

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

    if(node['key'] == k and node['priority'] == p):
        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, p)
    if(k < node['key']):
        node['left'] = delete(node['left'], k, p)
    else:
        node['right'] = delete(node['right'], k, p)

    return node

N,k = map(int, input().split())
arr = list(map(int,input().split()))
node = None
priorities = list(range(k))
shuffle(priorities)
for i in range(k):
    p = priorities.pop(0)
    node = insert(node, arr[i], p)
    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], p)
    node = insert(node, arr[i+k], p)
    priorities.append(p)

ans.append(find(node,INT_MAX))
print(" ".join([str(r) for r in ans]))

Submission status: Wrong Answer

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(k):
        update(A_bin_tree,i,arr[i],N)

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

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

Submission status: Wrong Answer

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: Wrong Answer

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

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


def printMax(arr, n, k): 
	max = 0
	
	for i in range(n - k + 1): 
		max = arr[i] 
		for j in range(1, k): 
			if arr[i + j] > max: 
				max = arr[i + j] 
		print(str(max) + " ", end = "") 


printMax(alist, N, L)

Submission status: Wrong Answer

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+1,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='')

Submission status: Wrong Answer

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+1,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='') 
    print(' ',end='')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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='')
print(answer)

Submission status: Wrong Answer

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):
    print(A[i*L:i*L+L])
    ans += str(min(A[i:i+L])) + " "
print(ans)

Submission status: Wrong Answer

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):
    print(A[i*L:i*L+L])
    ans += str(min(A[i:i+L])) + " "
print(ans[:-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [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: Wrong Answer

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+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]
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: Wrong Answer

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]
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: Wrong Answer

Solution code:
def binaryinsertion(A,x):
    left=0;right=len(A)-1;centre = len(A)//2
    while(True):
        if(right - left < 2):
            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: Wrong Answer

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 = [[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(search_min(Tree)[0])
    
print(" ".join(ANS))

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [""]*N

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [True]*N

Submission status: Wrong Answer

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-L+1)
for a in A:
    for i in range(L):
        try :
            if a[0] < int(ANS[a[1]-L+1+i]) :
                ANS[a[1]-L+1+i] = str(a[0])
        except IndexError :
            continue
    
print(" ".join(ANS))

Submission status: Wrong Answer

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 :
            ANS[a[1]+i] = str(a[0])
        except IndexError : continue
print(" ".join(ANS[L-1:]))

Submission status: Wrong Answer

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 = [True]*N
for j in range(N):
    a = heapq.heappop(A)
    for i in range(L):
        try :
            if ANS[a[1]+i] : ANS[a[1]+i] = str(a[0])
        except IndexError : continue
print(" ".join(ANS[L-1:]))

Submission status: Wrong Answer

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)
    try : A[x] += [i]
    except KeyError : A[x] =  [i]
for i in set(A) :
    for j in A[i] :
        for k in range(L) :
            try :
                if ANS[j+k] == 10**9+1 : ANS[j+k] = i
            except IndexError : continue       
for i in ANS[L-1:-1]:
    print(i, end=" ")
print(ANS[-1])

Submission status: Wrong Answer

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)
    try : A[x] += [i]
    except KeyError : A[x] =  [i]
for i in set(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: Wrong Answer

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)
    try : A[x] += [i]
    except KeyError : A[x] =  [i]
for i in set(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: Wrong Answer

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)
    try : A[x] += [i]
    except KeyError : A[x] = [i]
for i in set(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: Wrong Answer

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 set(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: Wrong Answer

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 + 2 : break
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N])

Submission status: Wrong Answer

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 + 2 : break

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

Submission status: Wrong Answer

Solution code:
import heapq
[N,L] = [int(x) for x in input().split()]
B = [0]*N
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
for i in A:
    B[i[1]] = i[0]

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 + 1000 > N : break

for i in range(L):
    if ANS[i] == 10**9+1 : ANS[i] = min(A[:i+1])
for i in range(L,N):
    if ANS[i] == 10**9+1 : ANS[i] = min(A[i+1-L:i+1])

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

Submission status: Wrong Answer

Solution code:
import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx <= end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.99 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
M = int(N ** 0.3)
K = N//M
for i in range(M+1) :
    ANS = SME(A, i*M, i*M+K, L, ANS)

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

Submission status: Wrong Answer

Solution code:
import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx <= end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.99 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
M = int(N ** 0.3)
K = N//M
for i in range(M) :
    ANS = SME(A, i*M, i*M+K, L, ANS)

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

Submission status: Wrong Answer

Solution code:
import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx <= end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.99 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
M = int(N ** 0.3)
K = N//M + 1
for i in range(M) :
    ANS = SME(A, i*M, i*M+K, L, ANS)

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

Submission status: Wrong Answer

Solution code:
import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx <= end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.99 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
start = 0
K = L * 2
if K > N : K = N
end = K
while (end <= N):
    ANS = SME(A, start, end, L, ANS)
    start = end
    end += K 
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

Submission status: Wrong Answer

Solution code:
import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx <= end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.99 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
start = 0
K = L * 3
if K > N : K = N
end = K
while (end <= N):
    ANS = SME(A, start, end, L, ANS)
    start = end
    end += K 
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

Submission status: Wrong Answer

Solution code:
import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx <= end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.99 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
start = 0
K = L * 5
if K > N : K = N
end = K
while (end <= N):
    ANS = SME(A, start, end, L, ANS)
    start = end
    end += K 
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

Submission status: Wrong Answer

Solution code:
import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx <= end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.99 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
start = 0
K = L + 1
if K > N : K = N
end = K
while (end <= N):
    ANS = SME(A, start, end, L, ANS)
    start = end
    end += K 
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

Submission status: Wrong Answer

Solution code:
import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx <= end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.99 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
start = 0
K = L * int(N ** 0.3 + 1 )
if K > N : K = N
end = K
while (end <= N):
    ANS = SME(A, start, end, L, ANS)
    start = end
    end += K 
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

Submission status: Wrong Answer

Solution code:
import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx <= end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.99 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
start = 0
K = L * int(N ** 0.3 + 2 )
if K > N : K = N
end = K
while (end <= N):
    ANS = SME(A, start, end, L, ANS)
    start = end
    end += K 
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

Submission status: Wrong Answer

Solution code:
import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if sum(ANS[a[1]:a[1]+L]) < (a[0]-1)*(L-1) + MAX + 1 :
            continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == MAX:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.995
MAX = 10**9+1
ANS = [MAX]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])