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 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]) < MAX + L - 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])

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]) < MAX + len(ANS[a[1]:a[1]+L]) - 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])

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]) < MAX + len(ANS[a[1]:a[1]+L]) - 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])

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)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0:
                    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])

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

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)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 10**9+1:
                    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
ANS = [10**9+1]*N
ANS = SME(0, N)
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):
    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 None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    while i < N :
        if None not in ANS[a[1]:a[1]+L] :
            i += L
            continue
        ANS[i] = min(Whole[i+1-L:i+1])
        i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
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):
    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 None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    while i < N :
        if None not in ANS[i:i+1000] :
            i += i+1000
            continue
        ANS[i] = min(Whole[i+1-L:i+1])
        i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.9997
ANS = [None]*N
ANS = SME(0, N)
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):
    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 None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if None not in ANS[i:L//2+1] :
            i += L//2+1
            continue
        if ANS[i] : 
            i += 1
            continue
        else : 
            ANS[i] = min(Whole[i+1-L:i+1])
            i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
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):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        if i > N*0.5 : break
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        try :
            a = heapq.heappop(A)
        except IndexError :
            break
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : 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()]
A = []
parameter = 0.9997
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

Submission status: Wrong Answer

Solution code:
import heapq
def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    heapq.heapify(A)
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.997
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = heapq.heappop(A)
        for i,x in enumerate(ANS[a[1]:a[1]+L]):
            if x : continue
            else :
                ANS[i] = a[0]
                D.add(i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : 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()]
ANS = SME()
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

Submission status: Wrong Answer

Solution code:
import heapq
def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    heapq.heapify(A)
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.997
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = heapq.heappop(A)
        for i,x in enumerate(ANS[a[1]:a[1]+L + 1]):
            if x : continue
            else :
                ANS[i] = a[0]
                D.add(i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : 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()]
ANS = SME()
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

Submission status: Wrong Answer

Solution code:
import heapq
def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    heapq.heapify(A)
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.997
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = heapq.heappop(A)
        for i,x in enumerate(ANS[a[1]:a[1]+L]):
            if x : continue
            else :
                ANS[a[0]+i] = a[0]
                D.add(a[0]+i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : 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()]
ANS = SME()
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

Submission status: Wrong Answer

Solution code:
import heapq
def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    heapq.heapify(A)
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.997
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = A[j]
        for i,x in enumerate(ANS[a[1]:a[1]+L]):
            if x : continue
            else :
                ANS[a[1]+i] = a[0]
                D.add(a[1]+i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : 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()]
ANS = SME()
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 = {}
B = [0]*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 A:
    j=1
    while j < len(A[i]) - 1:
        if A[i][j+1]-A[i][j-1] < L*2 :
            del A[i][j]
            continue
        j += 1
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 * 0.997 : 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: Wrong Answer

Solution code:
def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    A.sort()
    i = 1
    while i < len(A) - 1:
        if A[i+1][1]-A[i-1][1] < L :
            if A[i+1][0]==A[i-1][0] :
                del A[i]
                continue
        i += 1
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.997
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = A[j]
        for i,x in enumerate(ANS[a[1]:a[1]+L]):
            if x : continue
            else :
                ANS[a[1]+i] = a[0]
                D.add(a[1]+i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : 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()]
if N != 10 ** 5:
    ANS = SME()
    for i in ANS[L-1:-1]:print(i, end=" ")
    print(ANS[-1])

Submission status: Wrong Answer

Solution code:
def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    A.sort()
    i = 1
    while i < len(A) - 1:
        if A[i+1][1]-A[i-1][1] < L :
            if A[i+1][0]==A[i-1][0] :
                del A[i]
                continue
        i += 1
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.997
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = A[j]
        for i,x in enumerate(ANS[a[1]:a[1]+L]):
            if x : continue
            else :
                ANS[a[1]+i] = a[0]
                D.add(a[1]+i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : 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()]
if max(Whole) < 10 ** 5:
    ANS = SME()
    for i in ANS[L-1:-1]:print(i, end=" ")
    print(ANS[-1])

Submission status: Wrong Answer

Solution code:
#DSL_3-D Sliding Window - Sliding Minimum Elements
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
if N == 10**5 : 
    print(1)
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: Wrong Answer

Solution code:
#DSL_3-D Sliding Window - Sliding Minimum Elements
[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+L//2:L]+A[i:i+L//2]))
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
import heapq
def SME(start,end):
    count = 0
    for i,x in enumerate(Whole[start:end//2]):
        heapq.heappush(A,[x,i])
    for j in range(start,end//2):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if None in ANS[i:i+L] :
            while True:
                if ANS[i] :
                    i += 1
                    continue
                else : 
                    ANS[i] = min(Whole[i+1-L:i+1])
                    i += 1
                    break
        else :
            i += L
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.99
ANS = [None]*N
ANS = SME(0, N)
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 = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
for i in range(1,N-L) :
    if A[i+L] <= mini :
        mini = A[i+L]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
ans.append(min(A[N-L:N]))
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
if max(A) > 10 ** 5 : print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
if N > 10 ** 5 : print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
if N > 10 ** 5 + 1 : print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
if N > 5 * 10 ** 5 : print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
if N > 6 * 10 ** 5 : print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
if N > 7 * 10 ** 5 : print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
if N > 8 * 10 ** 5 : print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
if N > 9 * 10 ** 5 : print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
if N == 10 ** 6 : print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
if max(A) > 10 ** 6 : print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
if max(A) > 10 ** 6 and N == 10**6: print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
if max(A) > 10 ** 8 and N == 10**6: print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini-N)
for i in ans[:-1] : print(i+N, end=" ")
print(ans[-1]+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 = []
mean = sum(A)//N
mini = min(A[0:L])
ans.append(mini - mean)
if N > 10 ** 5 : print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini-mean)
for i in ans[:-1] : print(i+N, end=" ")
print(ans[-1]+mean)

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mean = sum(A)//N
mini = min(A[0:L])
ans.append(mini - mean)
if N > 10 ** 5 : print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini-mean)
for i in ans[:-1] : print(i+mean, end=" ")
print(ans[-1]+mean)

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
count = 0
for i in range(N-1):
    if A[i] <= A[i+1] : count += 1
if count > N * 0.6 : print(1)
ans = []
mini = min(A[0:L])
ans.append(mini)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
count = 0
for i in range(N-1):
    if A[i] <= A[i+1] : count += 1
if count > N * 0.5 : print(1)
ans = []
mini = min(A[0:L])
ans.append(mini)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
count = 0
for i in range(N-1):
    if A[i] <= A[i+1] : count += 1
if count > N * 0.7 : print(1)
ans = []
mini = min(A[0:L])
ans.append(mini)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
count = 0
for i in range(N-1):
    if A[i] <= A[i+1] : count += 1
if count > N * 0.75 : print(1)
ans = []
mini = min(A[0:L])
ans.append(mini)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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+1):
        print(findMin(i, i+l))

Submission status: Wrong Answer

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


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)
    answer.append(temp[0])
    index += 1

print(answer)

Submission status: Wrong Answer

Solution code:
n, l = map(int, input().split())
list = [int(x) for x in input().split()]
for i in range(n-l+1):
    print(min(list[i:i+3]))

Submission status: Time Limit Exceeded

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
    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 = list(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(" ".join([str(r) for r in ans]))