Problem:
 Score : 500 points    Problem Statement We have N bulbs arranged on a number line, numbered 1 to N from left to right.
Bulb i is at coordinate i .  Each bulb has a non-negative integer parameter called intensity.
When there is a bulb of intensity d at coordinate x , the bulb illuminates the segment from coordinate x-d-0.5 to x+d+0.5 .
Initially, the intensity of Bulb i is A_i . We will now do the following operation K times in a row:   For each integer i between 1 and N (inclusive), let B_i be the number of bulbs illuminating coordinate i . Then, change the intensity of each bulb i to B_i .   Find the intensity of each bulb after the K operations.      Constraints  1 \leq N \leq 2 \times 10^5  1 \leq K \leq 2 \times 10^5  0 \leq A_i \leq N         Input Input is given from Standard Input in the following format:  N  K  A_1  A_2  \ldots  A_N       Output Print the intensity A{'}_i of each bulb i after the K operations to Standard Output in the following format:  A{'}_1  A{'}_2  \ldots  A{'}_N         Sample Input 1 5 1
1 0 0 1 0      Sample Output 1 1 2 2 1 2  Initially, only Bulb 1 illuminates coordinate 1 , so the intensity of Bulb 1 becomes 1 after the operation.
Similarly, the bulbs initially illuminating coordinate 2 are Bulb 1 and 2 , so the intensity of Bulb 2 becomes 2 .       Sample Input 2 5 2
1 0 0 1 0      Sample Output 2 3 3 4 4 3

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

for i in range(k):
    res = [0]*(n+2)
    for j in range(n):
        l = max(-1,j - lst1[j])
        r = min(n,j + lst1[j] + 1)
        res[l+1] += 1
        res[r+1] -= 1
    for j in range(1,n+1):
        res[j] += res[j-1]
    lst1 = res[1:n+1]
    if lst1[0] == lst1[-1] == n:
        break
    

print(*lst1)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
def ligh(li):
  for x in range(k):
    if li==[n]*n:
      return li
    ne=[0]*(n+1)
    zr=[]
    lis=[]
    for (i,a) in zip(range(n),li):
      if a==0:
        zr.append(i)
      else:
        ne[max(0,i-a)]+=1
        ne[min(i+a+1,n)]-=1

    for i in range(1,n):
      ne[i]+=ne[i-1]
    for i in zr:
      ne[i]+=1
    li=ne[:-1]
    
  return li

for i in ligh(a):
  print(i,end=" ")

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math


MOD = 10 ** 9 + 7



N, k = map(int, input().split())
prev_arr = list(map(int, input().split()))




count = 0
for i in range(min(k, 3*int(math.log(N))+5)):
    que = []
    arr = [0]*N
    for j in range(N):
        heapq.heappush(que, j+prev_arr[j])
        while que[0] < j:
            heapq.heappop(que)
        arr[j] += len(que)
    

    que = []
    for j in reversed(range(N)):
        heapq.heappush(que, -(j-prev_arr[j]))
        while -que[0] > j:
            heapq.heappop(que)
        arr[j] += len(que) - 1

    prev_arr = arr
    count += 1


print(*prev_arr)

Solution (Python):
def update(a, n):
    ret = [0] * (n+1)
    for i in range(n):
        l = max(0, i - a[i])
        r = min(i + a[i] + 1, n)
        ret[l] += 1
        ret[r] -= 1
    data = [0] * (n+1)
    data[0] = ret[0]
    for i in range(1, n+1):
        data[i] = data[i-1] + ret[i]
    return data[:-1]


n, k = map(int, input().split())
ret = list(map(int, input().split()))

k = min(k, 120)

for i in range(k):
    ret = update(ret, n)

print(' '.join(list(map(str, ret))))

Solution (Python):
from collections import deque

n,k=map(int,input().split())
A=list(map(int,input().split()))
for i in range(min(k,50)):
    P=[]
    M=[]
    cnt=0
    for a in range(n):
        if A[a]==n:
            cnt+=1
            continue
        P.append(a-A[a])
        M.append(a+A[a]+1)
    P.sort()
    M.sort()
    P=deque(P)
    M=deque(M)
    C=[]
    m=n
    for j in range(n):
        if P:
            while P[0]<=j:
                P.popleft()
                cnt+=1
                if not P:
                    break
        if M:
            while M[0]<=j:
                M.popleft()
                cnt-=1
                if not M:
                    break
        C.append(cnt)
        m=min(cnt,m)
    A=C
    if m==n:
        break
print(*A)

Solution (Python):


LI = lambda: list(map(int, input().split()))


N, K = LI()
A = LI()


def main():
    ans = A.copy()
    w = [0] * (N + 1)
    for i in range(N):
        w[max(0, i - A[i])] += 1
        w[min(N, i + A[i] + 1)] -= 1
    
    for _ in range(K):
        x = 0
        l = [0] * (N + 1)
        flag = True
        for i in range(N):
            x += w[i]
            if x != N:
                flag = False
            ans[i] = x
            l[max(0, i - x)] += 1
            l[min(N, i + x + 1)] -= 1
        if flag:
            break
        w = l
    
    print(*ans)


if __name__ == "__main__":
    main()

Solution (Python):
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

ans = A
for k in range(K):
    temp = [0 for _ in range(N)]
    for i in range(N):
        a = ans[i]
        temp[max(i-a, 0)] += 1
        if i + a + 1 < N:
            temp[i+a+1] -= 1

    ans[0] = temp[0]
    for j in range(1, N):
        ans[j] = ans[j-1] + temp[j]

    if ans.count(N) == N:
        break

for i in range(N):
    print(ans[i], end=" ")

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

for i in range(K):
  R = [ {} for j in range(N)]

  for j in range(N):
    s = A[j]
    
    if min(j+s, N-1) in R[max(0, j-s)]:
      R[max(0, j-s)][min(j+s, N-1)] += 1
    else:
      R[max(0, j-s)][min(j+s, N-1)] = 1
        
  
  
  L = [0 for j in range(N)]
  t = 0
  for j in range(N):
    r = R[j]
    for k, v in r.items():
      t += v
      L[k] += v
    A[j] = t
    t -= L[j]
    
  if A[0] == N and A[-1] == N:
    for j in range(N):
      if A[j] < N:
        break
    else:
      break
print(*A)

Solution (Python):
import copy

N, K = map(int, input().split())
a = list(map(int, input().split()))

ans = [0] * N
def loop():
    global a
    ruir = [0] * (N + 1)
    ruil = [0] * (N + 1)
    for i in range(N):
        ruir[i] += 1
        tmp = i + a[i]
        if tmp < N:
           ruir[tmp + 1] -= 1
    for i in range(N):
        ruir[i + 1] += ruir[i]

    for i in reversed(range(N)):
        if a[i] - 0.5 > -1:
            ruil[i - 1] += 1
            tmp = i - a[i]
            if tmp > 0:
                ruil[tmp - 1] -= 1
    for i in reversed(range(N)):
        ruil[i - 1] += ruil[i]
    cnt = 0
    for i in range(N):
        add = ruir[i] + ruil[i]
        if add > N:
            add = N
        if add == N:
            cnt +=1
        ans[i] = add
    if cnt == N:
        print(*ans)
        exit()
    a = copy.deepcopy(ans)

for i in range(K):
    loop()
print(*ans)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
from copy import copy

for k in range(K):
    left={}
    right={}
    for i in range(N):
        l=max(0,i-A[i])
        r=min(N-1,i+A[i])
        if l in left:
            left[l]+=1
        else:
            left[l]=1
        if r in right:
            right[r]+=1
        else:
            right[r]=1

    br=[]
    b=0
    m=N
    for i in range(N):
        if i in left:
            b+=left[i]
        br.append(b)
        m=min(m,b)
        if i in right:
            b-=right[i]
    if m==N:
        break
    A=copy(br)
print(*br)

Solution (Python):
import copy

N, K = map(int, input().split())
a = list(map(int, input().split()))

ans = [0] * N
def loop():
    global a
    ruir = [0] * (N + 1)
    ruil = [0] * (N + 1)
    for i in range(N):
        ruir[i] += 1
        tmp = i + a[i]
        if tmp < N:
           ruir[tmp + 1] -= 1
    for i in range(N):
        ruir[i + 1] += ruir[i]

    for i in reversed(range(N)):
        if a[i] - 0.5 > -1:
            ruil[i - 1] += 1
            tmp = i - a[i]
            if tmp > 0:
                ruil[tmp - 1] -= 1
    for i in reversed(range(N)):
        ruil[i - 1] += ruil[i]
    cnt = 0
    for i in range(N):
        add = ruir[i] + ruil[i]
        if add > N:
            add = N
        if add == N:
            cnt +=1
        ans[i] = add
    if cnt == N:
        print(*ans)
        exit()
    a = copy.deepcopy(ans)

for i in range(K):
    loop()
print(*ans)

Solution (Python):
def main():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))

    for _ in range(min(K,50)):
        e_list_1 = [0] * N
        l_1 = [0] * N
        v = 0
        for i,a in enumerate(A_list):
            l_1[i] = v 
            e_list_1[min(i + a, N-1)] += 1
            v = v + 1 - e_list_1[i]
        
        e_list_2 = [0] * N
        v = 0
        for _i,a in enumerate(A_list[::-1]):
            i = N-1-_i
            A_list[i] = l_1[i] + v + 1
            e_list_2[max(i-a, 0)] += 1
            v = v + 1 - e_list_2[i]
        
    print(*A_list)
if __name__ == "__main__":
    main()

Solution (Python):
N, K = map(int, input().split())
A = [int(s) for s in input().split()]

a = [0] * N
for k in range(K):
    for i in range(N):
        a[max(0, i - A[i])] += 1
        if N - 1 >= (A[i] + i + 1):
            a[A[i] + i + 1] -= 1

    if a[0] == N:
        A = [N] * N
        break
    for j in range(N):
        A[j] = A[j - 1] if j > 0 else 0
        A[j] += a[j]
        a[j] = 0
    


for i in range(N):
    print(A[i], end="")
    if i < N - 1:
        print(" ", end="")
print()

Solution (Python):
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import itertools
gcd = math.gcd
n,k = ma()
A = list(ma())
def imos(ls,st,ed):
    n = len(ls) -2
    for i in range(n):
        if 0< st[i]:
            ls[st[i]] += 1
        else:
            ls[0] +=1
        if ed[i] <=n:
            ls[ed[i]+1] -=1
        else:
            ls[n+1] -=1
    for i in range(n+1):
        ls[i+1] += ls[i]
low = []
high = []
ls = [0]*(n+2)
for i in range(n):
    a = A[i]
    low.append(i+1-a)
    high.append(i+1+a)
for i in range(k):
    imos(ls,low,high)
    if ls[1:-1] == [n]*n:
        break
    
    if i==k-1:break
    for j in range(n):
        a = ls[j+1]
        low[j] = j+1-a
        high[j] = (j+1+a)
    ls = [0]*(n+2)
print(*ls[1:-1])

Solution (Python):
from decimal import *
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())



def solve(N, K, A):
    def update():
        new_A = [0]*N
        end_idx = [0]*N
        num_act = 0
        num_max = 0
        for i in range(N):
            end_idx[min(i+A[i], N-1)]+=1
            num_act+=1
            new_A[i] = num_act
            num_act-=end_idx[i]
        end_idx = [0]*N
        num_act = 0
        num_max = 0
        for i in range(N-1, -1, -1):
            tmp = A[i]
            new_A[i]+= num_act
            if new_A[i] == N:
                num_max+=1
            if A[i]>0:
                num_act += 1
                end_idx[max(0,i-tmp)]+=1
            num_act -= end_idx[i]
        return new_A, num_max
    for _ in range(K):
        A, num_max = update()
        if num_max == N:
            return [str(n) for n in A]
    return [str(n) for n in A]
    



N, K = rrm()
A = rrm()
ans = solve(N, K, A)
print(' '.join(ans))

Solution (Python):
N,K = list(map(int, input().split()))
A = list(map(int, input().split()))

from itertools import accumulate

if N-min(A) <= K:
    print(*[N]*N)
    exit()
    
ans=[0]*(N+1)
for _ in range(K):
    for i,a in enumerate(A):
        ans[max(0,i-a)]+=1
        ans[min(i+a+1,N)]-=1
    A = list(accumulate(ans))[:-1]
    ans=[0]*(N+1)
    if all(i == N for i in A):
        break
print(*A)

Solution (Python):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))
n,k = l_in()
A = l_in()


t = 0
while t < k:
    left = [0]*n
    right = [0]*n

    
    for i, a in enumerate(A):
        left[max(i-a,0)] += 1
        right[min(i+a,n-1)] += 1

    flag = True
    A = [0]*n
    current = 0
    for i in range(n):
        current += left[i]
        A[i] = current
        flag = flag and A[i] == n
        current -= right[i]

    t += 1

    if flag:
        break

    

print(*A)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



from itertools import accumulate 
import math
    
N, K = mi()
A = li()
 



'''
thre = 0
for i in range(N):
    if A[i] < i:
        thre = max(thre, i-A[i])
'''
if K > pow(N, 0.5) + 1:
        for i in range(N):
            print(N, '', end='')
        print()
        exit()
 
 
for i in range(K):
    new = [0] * (N+1)
    for j in range(N):
        new[max(j-A[j], 0)] += 1
        new[min(j+A[j]+1, N)] += -1
        
    new = list(accumulate(new))
    A = new[:N]
 
for i in range(N):
    print(A[i], '', end='')
print()

Solution (Python):
n,k,*a=map(int,open(0).read().split())
r=range(n)
while k:
 k-=1;b=[0]*n*3
 for i in r:t=a[i];b[max(0,i-t)]+=1;b[i-~t]-=1
 for i in r:b[i+1]+=b[i]
 a=b[:n]
 if min(a)==n:break
print(*a)

Solution (Python):
n,k,*a=map(int,open(0).read().split())
r=range(n)
while k:
 k-=1;b=[0]*-~n
 for i in r:t=a[i];b[max(0,i-t)]+=1;b[min(n,i-~t)]-=1
 for i in r:b[i+1]+=b[i]
 a=b[:n]
 if min(a)==n:break
print(*a)

Solution (Python):
import sys
def main(N, K, A):
    for k in range(min(50, K)):
        C = [0] * (N + 1)
        for i in range(N):
            a = A[i]
            C[max(0, i - a)] += 1
            C[min(N, i + a + 1)] -= 1
        A[0] = C[0]
        for i in range(1, N):
            A[i] = A[i - 1] + C[i]
    return A

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(int, input().split())
    print(*main(N, K, A))

Solution (Python):
import sys
import itertools

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    
    K = min(50, K)
    for i in range(K):
        B = [0]*N
        for j in range(N):
            st = max(0, j - A[j])
            ed = j + A[j] + 1
            B[st] += 1
            if ed < N:
                B[ed] -= 1
        Bcum = itertools.accumulate(B)
        A = list(Bcum)
    print(*A)

if __name__ == "__main__":
    main()

Solution (Python):
from copy import deepcopy
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(k):
    b = [0] * (n+1)
    for i in range(n):
        b[max(0, i-a[i])] += 1
        b[min(n, i+a[i]+1)] -= 1
    for i in range(n-1):
        b[i+1] += b[i]
    b.pop()
    a = deepcopy(b)
    
    if bisect.bisect_left(a, n) == 0: break
    
print(*a)

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def dd(al,n):
	imos=[0]*(n+1)
	for i, v in enumerate(al):
		imos[max(0, i-v)]+=1
		imos[min(n, i+v+1)]-=1
	ret = [0]*(n)
	ret[0]=imos[0]
	mmm=0
	for i, v in enumerate(imos[1:-1],1):
		ret[i]=ret[i-1]+imos[i]
	return ret, min(ret)



def main():
	
	n, k = tin()
	
	al=lin()
	for _ in range(k):
		nal, min_al = dd(al,n)
		if min_al == n:
			print(*nal)
			return
		al=nal
	print(*nal)
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
from itertools import accumulate
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))

    for _ in range(K):
        data = [0] * len(A)
        for i in range(N):
            range_mai = i - A[i]
            range_pura = i + A[i]
            if range_mai < 0:
                range_mai = 0
            if range_pura > N - 1:
                range_pura = N - 1
            data[range_mai] += 1
            if range_pura + 1 != N:
                data[range_pura + 1] -= 1

        A = list(accumulate(data))
        if min(A) == N:
            break
    print(*A)

if __name__ == "__main__":
    main()

Solution (Python):
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
n,k=mi()
a=li()
for i in range(k):
    tmp=[0]*n
    for j in range(n):
        x1=max(0,j-a[j])
        x2=min(n+1,j+a[j])
        tmp[x1]+=1
        if(x2<n-1):
            tmp[x2+1]-=1
       
    f=1
    a[0]=tmp[0]
    if(a[0]<n):
        f=0
    for j in range(1,n):
        tmp[j]+=tmp[j-1]
        a[j]=tmp[j]
        if(a[j]<n):
            f=0
    if(f):
        break
print(*a)

Solution (Python):
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))


def calc_imos(arr):
    imos = [0] * (N + 1)
    for i, a in enumerate(arr):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        imos[l] += 1
        imos[r + 1] -= 1
    imos = list(accumulate(imos))
    return imos[:-1]


for k in range(min(50, K)):
    A = calc_imos(A)
print(*A, sep=' ')

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

for _ in range(K):
    tmp = [0] * (N+1)
    for i in range(N):
        tmp[max(0, i-A[i])] += 1
        tmp[min(N-1, i+A[i]) + 1] -= 1

    ans = [0]*N
    A[0] = tmp[0]
    for i in range(1, N):
        A[i] = A[i-1] + tmp[i]

    
    if sum(A) == N*N:
        break
print(*A)

Solution (Python):
N,K = map(int,input().split())
A = [int(i) for i in input().split()]
three_hold_list = [0] *(3*N)
ans = ans = [N] * N
if K >= N :
    print(*ans)
else:
    for i in range(K):
        Accum = [0] *(3*N)
        for j in range(N):
            Accum[N+j-A[j]] += 1
            Accum[N+j+A[j]+1] -= 1
        num = 0
        for l in range(3*N):
            num += Accum[l]
            three_hold_list[l] = num
        if three_hold_list[N:2*N] == ans:
            break
        else:
            A = three_hold_list[N:2*N]
    print(*three_hold_list[N:2*N])

Solution (Python):
import itertools

n,k= map(int, input().split())
a= list(map(int, input().split()))
if k>=50:
    ans=[n]*n
    print(*ans)
    exit()

ans=[0]*(n+1)

for i in range(k):
    ansx=[0]*(n+1)
    for j in range(n):
        if i==0:
            ansx[max(j - a[j], 0)] += 1
            ansx[min(n, j + a[j] + 1)] -= 1
        else:
            ansx[max(j - ans[j], 0)] += 1
            ansx[min(n, j + ans[j] + 1)] -= 1

    ansx = list(itertools.accumulate(ansx))
    ans=ansx


print(*ans[:n])

Solution (Python):
N, K = map(int, input().split())
s = input()
res = list(map(int,s.split()))

for k in range(K):
    delta = [0]*(N+1)
    for i,val in enumerate(res):
        left = max(0, i-val)
        right = min(N, i+val+1)
        delta[left] += 1
        delta[right] -= 1
    res = [0]*N
    res[0] = delta[0]
    for i in range(N-1):
        res[i+1] = res[i]+delta[i+1]
    if delta[0] == -delta[N] == N:
        break

print(*res)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))

try_count = min(50, k)

for i in range(try_count):
    imos_up = [0 for _ in range(len(a))]
    imos_down = [0 for _ in range(len(a))]
    for j in range(len(a)):
        up = max(0,j-a[j])
        imos_up[up] += 1
        down = min(len(a)-1, j+a[j])
        imos_down[down] += 1
    now = 0
    for j in range(len(a)):
        now += imos_up[j]
        a[j] = now
        now -= imos_down[j]

print(" ".join(list(str(s) for s in a)))

Solution (Python):
from random import randint
n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(k):
    cur = 0
    new_a = [-1]*n
    end = [0]*n
    for j in range(n):
        cur += 1
        new_a[j] += cur
        end[min(j+a[j],n-1)] += 1
        cur -= end[j]
    end = [0]*n
    for j in range(n)[::-1]:
        cur += 1
        new_a[j] += cur
        end[max(j-a[j],0)] += 1
        cur -= end[j]
    a = new_a
    if a[0] == n:
        print(*[n]*n)
        exit()
print(*a)

Solution (Python):
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
ex=0
for test in range(K):
    ex+=1
    D=[0 for i in range(N+1)]
    for i in range(N):
        D[max(0,i-A[i])]+=1
        D[min(N,i+A[i]+1)]-=1
    A[0]=D[0]
    for i in range(1,N):
        A[i]=A[i-1]+D[i]
    if set(A)=={N}:
        break
print(*A)

Solution (Python):
import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
if K >= 50:
    print(*[N]*N)
    exit()
for i in range(K):
    newA = [0]*N
    for j in range(N):
        newA[max(0,j-A[j])] += 1
        if j+A[j]+1 < N:
            newA[min(N-1,j+A[j]+1)] -= 1
    A = list(itertools.accumulate(newA))
    if A == [N]*N:
        break
print(*A)

Solution (Python):
import numpy as np

N, K = map(int, input().split(' '))
A = tuple(map(int, input().split(' ')))
indexes = np.arange(0, N)

dp = np.zeros(shape=N + 1, dtype=np.int64)

for k in range(K):
    np.add.at(dp, np.maximum(0, indexes - A), 1)
    np.add.at(dp, np.minimum(N, indexes + A + 1), -1)
    A = dp.cumsum()[:-1]
    if np.all(A == N):
        break
    dp *= 0

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

Solution (Python):
import itertools

N, K = map(int,input().split())
A = list(map(int,input().split()))
B = [0] * (N+1)
chk = [N] *N
for k in range(K):
    if A == chk:
        break
    for i in range(N):
        if A[i] == 0:
            B[i] += 1
            B[i+1] -= 1
            continue
        l = i - A[i]
        r = i + A[i]
        if l <= 0:
            B[0] += 1
        else:
            B[l] += 1
        if r >= N-1:
            B[N] -= 1
        else:
            B[r+1] -= 1        
    A = list(itertools.accumulate(B))[:-1]
    B = [0] * (N+1)
print(*A)

Solution (Python):
import sys
input = sys.stdin.readline
n,K = map(int,input().split())
a = list(map(int,input().split()))

for k in range(K):
    light = [0]*n
    st = [0]*n
    skip = True
    for i in range(n):
        if i - a[i] >= 0:
            light[i-a[i]] += 1
        else:
            light[0] += 1
        
        if i + a[i] + 1 <= n-1:
            light[i + a[i] + 1] -= 1

    st[0] = light[0]
    if st[0] < n-1:
        skip = False
    for i in range(1,n):
        st[i] = st[i-1] + light[i]
        if st[i] < min(n-1-i,i):
            skip = False
    
    if skip:
        if k < K-1:
            for _ in range(n):
                print(n,end =" ")
            exit()
        else:
            for ans in st:
                print(ans, end = " ")
            exit()
    a = st[::]
for ans in a:
    print(ans, end = " ")

Solution (Python):
import math
n , k = map(int, input().split())
a = list(map(int,input().split()))
a1=[0]*(n+1)
k = min(k,int(math.log2(n)*2.5))
for i in range(k):
    for j in range(n):
        st=j-a[j]
        gl=j+a[j]
        if st<0:
            st=0
        if gl>=n:
            gl=n-1
        a1[st]+=1
        a1[gl+1]-=1
    for k in range(1,n):
        a1[k]=a1[k-1]+a1[k]
    a=a1[:n]
    a1=[0]*(n+1)
print(' '.join([str(n) for n in a]))

Solution (Python):
import sys
import heapq
import random
import collections






def solve(k,lst):  
    console("----- solving ------")

    arr = [0 for _ in lst]
    for _ in range(min(k,50)):
        uppp = [0 for _ in range(len(lst)+1)]
        down = [0 for _ in range(len(lst)+1)]
        for i,x in enumerate(lst):
            uppp[max(0,i - x)] += 1
            down[min(len(lst),i + x + 1)] += 1
        
        
        
        cur = 0
        for i,x in enumerate(arr):
            cur += uppp[i]
            cur -= down[i]
            arr[i] = cur
        
        
        
        lst = arr

    return " ".join([str(x) for x in lst])


def console(*args):  
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return



    
    

    
    
    
    
    

    
_,k = list(map(int,input().split()))
lst = list(map(int,input().split()))

    
    
    
    
    
    

res = solve(k,lst)  
    
    
    

    
print(res)

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    cur = A
    for _ in range(K):
        prev = cur
        cur = [0] * N
        pls = [0] * (N+1)
        for i in range(N):
            l = max(i - prev[i], 0)
            r = min(i + prev[i], N-1)
            pls[l] += 1
            pls[r+1] -= 1
        num = 0
        for i in range(N):
            num += pls[i]
            cur[i] = num
        same = True
        for i in range(N):
            if cur[i] != prev[i]:
                same = False
                break
        if same:
            break
    print(*cur)


if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect_left
N, K = map(int, input().split())
As = list(map(int, input().split()))

if K >= 40:
    print(' '.join(map(str, [N]*N)))
    exit()

for _ in range(K):
    events = [[] for _ in range(N*2+2)]
    for i, a in enumerate(As):
        l = 2*(i-a)-1
        r = 2*(i+a)+1
        events[-1 if l < -1 else l].append(i)
        events[N*2 if r > N*2 else r].append(i)
    active = [0] * N
    L = 0
    nextAs = [0] * N
    for i in range(N):
        for k in events[2*i-1]:
            if active[k]:
                active[k] = 0
                L -= 1
            else:
                active[k] = 1
                L += 1
        nextAs[i] = L
    As = nextAs

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

Solution (Python):
n, k = [int(_) for _ in input().split(' ')]
a = [int(_) for _ in input().split(' ')]

for _ in range(k):
    diff = [0 for _ in range(n + 1)]
    for i in range(n):
        diff[max(i - a[i], 0)] += 1
        diff[min(i + 1 + a[i], n)] -= 1

    for i in range(n):
        if i == 0:
            a[i] = diff[0]
        else:
            a[i] = a[i - 1] + diff[i]
    
    if all([d == n for d in a]):
        break

print(' '.join([str(d) for d in a]))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k = map(int,readline().split())
A = list(map(int,readline().split()))

class SegmentTree:
    def __init__(self, n, ele, segfun):
        
        self.ide_ele = ele
        self.segfun = segfun
        
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [self.ide_ele] * (self.N0 * 2)
        
    def update_add(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] += val
                l += 1
            if r & 1:
                self.data[r - 1] += val
                r -= 1
            l //= 2
            r //= 2

    def update(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.segfun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r - 1] = self.segfun(self.data[r - 1], val)
                r -= 1
            l //= 2
            r //= 2

    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.segfun(ret, self.data[i])
        return ret

for i in range(k):
  m = n
  S = SegmentTree(n,0,lambda a, b: a+b)
  for j in range(n):
    q = A[j]
    m = min(m,q)
    S.update_add(max(1,j-q+1),min(n+1,j+q+2), 1)
  if i < k-1 and m >= n-1:
    A = [n]*n
    break
  for l in range(n):
    p = S.query(l+1)
    A[l] = p
    
print(*A)

Solution (Python):
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

ans = [[0, A[i]] for i in range(N)]
idx = 1
for k in range(K):
    for i in range(N):
        ans[i][k%2] = 0
    for i in range(N):
        ans[max(0, i-ans[i][(k+1)%2])][k%2] += 1
        if i+ans[i][(k+1)%2] < N-1:
            ans[i+ans[i][(k+1)%2]+1][k%2] -= 1
    for i in range(N-1):
        ans[i+1][k%2] += ans[i][k%2]
    idx += 1
    idx %= 2
    if ans[0][k%2] == N:
        break

ans2 = [0]*N
for i in range(N):
    ans2[i] = ans[i][idx]
    
print(*ans2)

Solution (Python):
n,k = map(int,input().split())
dp = list(map(int,input().split()))
if k > 1000:
  ans = [n for _ in range(n)]
  print(*ans)
else:
  for i in range(k):
    ndp = [0 for _ in range(n)]
    for j in range(n):
      if j-dp[j] < 0:
        ndp[0] += 1
      else:
        ndp[j-dp[j]] += 1
      if j+dp[j]+1 < n:
        ndp[j+dp[j]+1] -= 1
    for j in range(1,n):
      ndp[j] += ndp[j-1]
    dp = ndp[:]
  print(*dp)

Solution (Python):
def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()

Solution (Python):
"""
愚直にやるなら、操作のたびに、各座標ごとに照らしている電球の個数をカウントする。
1回の操作でこの作業をするのに、O(N^2)かかる。
K回やるなら、O(KN^2)かかる。

まず、各座標ごとに照らしている電球の個数はいくつか？というカウント作業を短縮する必要がある。
これを短縮しないと、初期状態の把握すら困難。
O(N)くらいでできないだろうか -> imosつかえばできる。


いや、各座標ごとに照らしている電球がいくつあるのかはそもそも把握不可能ではないのか？
長さNの配列を用意して、各座標ごとに


順番に1ずつ増えていく気配。
とりあえず、最初の配列の段階で


imosが使えるのでは？


で、これ最初全部の光の強さが0だとしても、操作はlogN+a回以内に終わる。
のでimosで毎回各座標を照らす電球の個数を計算していけば、答えにたどり着ける

"""

N,K = map(int,input().split())
A = list(map(int,input().split()))

for _ in range(K):
    imos = [0]*(N+1)
    for i in range(N):
        d = A[i]
        
        l = max(0,i-d)
        
        r = min(N-1,i+d)

        
        ls = l
        lt = i
        rs = i+1
        rt = r+1
        imos[ls]+=1
        imos[lt]+=-1
        imos[rs]+=1
        imos[rt]+=-1
    for i in range(1,N):
        imos[i] += imos[i-1]
    
    for i in range(N):
        imos[i] += 1
    
    A = imos
    if A.count(N)>=N:
        break
ans = []
for i in range(N):
    ans.append(str(A[i]))
print(" ".join(ans))

Solution (Python):

import copy
N,K=map(int,input().split())
A=list(map(int,input().split()))
for k in range(K):
    imos=[0 for i in range(N+1)]
    
    for i in range(N):
        imos[max(i-A[i],0)]+=1
        imos[min(i+A[i]+1,N)]-=1
    tmp=[imos[0]]
    for i in range(N-1):
        tmp.append(tmp[i]+imos[i+1])
    A=copy.deepcopy(tmp)
    if set(A)==set([N]):
        break
    
print(*A)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
over = [N]*N

for k in range(K):
    data = [0] * N
    for i in range(N):
        l = max(0, i-A[i])
        r = min(N-1, i+A[i])
        data[l] += 1
        if r+1 != N:
            data[r+1] -= 1
    ruiseki = [0] * N
    ruiseki[0] = data[0]
    for i in range(1, N):
        ruiseki[i] = ruiseki[i-1] + data[i]
    A = ruiseki
    if A == over:
        print(*A)
        exit()

print(*A)