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):
def solve(n, k, a_list):

    for t in range(k):

        left_list = [0] * n
        right_list = [0] * n

        for i in range(n):
            left = i - a_list[i] - 1
            if left >= 0:
                left_list[left] += 1
            right = i + a_list[i] + 1
            if right < n:
                right_list[right] += 1

        a_list = [n] * n

        if sum(left_list) == 0 and sum(right_list) == 0:
            break

        
        right_erase = 0
        for i in range(n):
            right_erase += right_list[i]
            a_list[i] -= right_erase
        
        left_erase = 0
        for i in range(n - 1, -1, -1):
            left_erase += left_list[i]
            a_list[i] -= left_erase

    return " ".join([str(a) for a in a_list])


def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    res = solve(n, k, a_list)
    print(res)


def test():
    assert solve(5, 1, [1, 0, 0, 1, 0]) == "1 2 2 1 2"
    assert solve(5, 2, [1, 0, 0, 1, 0]) == "3 3 4 4 3"


if __name__ == "__main__":
    test()
    main()

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

for i in range(K):
  new = [0] * (N+1)
  for j in range(N):
    new[max(0, j-A[j])] += 1
    if j+A[j]+1 <= N-1:
      new[j+A[j]+1] -= 1
  A[0] = new[0]
  for j in range(1, N):
    new[j] += new[j-1]
    A[j] = new[j] 
  for ai in A:
    if ai != N:
      break
  else:
    break
    
print(' '.join([str(ai) for ai in A]))

Solution (Python):
def solve(A,N,K):
    for k in range(K):
        C = [0 for _ in range(N+1)]
        
        for i in range(N):
            C[max(i-A[i],0)] += 1
            C[min(i+A[i]+1,N)] -= 1
        for i in range(1,N):
            C[i] += C[i-1]

        if C[0] == N or C[N-1] == N:
            for i in range(N):
                A[i] = N
            break
        else:
            for i in range(N):
                A[i] = C[i]
    return A

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

    ans = solve(A,N,K)

    print(" ".join(map(str,ans)))

if __name__ == "__main__":
    main()

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

def main():
    for k in range(K):
        li = [0 for i in range(N+1)]
        rsl = [0 for i in range(N+1)]


        for i in range(N):
            if A[i] != 0:
                li[max(0,i-A[i])]+= 1
                li[min(N,i+A[i]+1)]-= 1
        
        mm = 0
        for i in range(N):
            mm += li[i]
            if A[i]>0:
                A[i] = mm
            else:
                A[i] = mm +1
        

        if min(A)>=N:
            break
    print(*A)



main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


from functools import lru_cache


def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]

class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        for i,x in enumerate(seq,1):
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += x
            i += i & -i
    
    def find_kth_element(self,k):
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
 
def main():
    mod = 1000000007
    

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

    bit=[0]*(N+2)
    for i,a in enumerate(A):
        i+=1
        left=max(i-a,0)
        right=min(i+a+1,N+1)
        bit[left]+=1
        bit[right]-=1
    
    for k in range(K):
        update=[0]*N
        nA=copy(A)
        ax=accumulate(bit)
        
        
        next(ax)
        for i in range(N):
            a=A[i]
            na=next(ax)
            

            if a!=na:
                nA[i]=na
                update[i]=1


        
        if sum(update)==0:
            break

        for i, a in enumerate(A):
            if update[i]==0:
                continue
            na=nA[i]
            i+=1

            left=max(i-a,0)
            right=min(i+a+1,N+1)
            bit[left]-=1
            bit[right]+=1
            left=max(i-na,0)
            right=min(i+na+1,N+1)
            bit[left]+=1
            bit[right]-=1

        A=nA
    
    print(*nA)

        





if __name__ == "__main__":
    main()

Solution (Python):
def main():
    from sys import stdin
    input = stdin.readline

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    for cnt in range(min(k, 41)):
        ans = []
        bit = [0]*(n+1)
        for i, j in enumerate(a):
            x, y = max(i-j, 0)+1, min(i+j+1, n)+1
            while x < n+1:
                bit[x] += 1
                x += x & (-x)
            while y < n+1:
                bit[y] -= 1
                y += y & (-y)
        for i in range(n):
            ret, x = 0, i+1
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            ans.append(ret)
        a = ans

    print(*ans)


main()

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
imos = [0]*(2*10**5+1)
for j in range(min(k,700)):
    imos = [0]*(2*10**5+1)
    for i in range(n):
        imos[max(i-a[i],0)] += 1
        imos[min(i+a[i]+1,2*10**5)] -= 1
    for i in range(1,n):
        imos[i] += imos[i-1]
    a = imos
print(*imos[:n])

Solution (Python):
N, K = [int(x) for x in input().split(' ')]
A = [int(x) for x in input().split(' ')]
N = len(A)

S = A
D = [0] * N
for _ in range(K):
  for x in range(N):
    D[x] = 0
  for x in range(N):
    D[max(0, x - S[x])] += 1
    if(x + S[x] + 1 < N):
      D[x + S[x] + 1] -= 1
  S[0] = D[0]
  for x in range(1, N):
    S[x] = S[x-1] + D[x]
  if all([x == N for x in S]):
    break
      
print(' '.join([str(x) for x in S]))

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


for k in range(K):
    if all(a==N for a in A):
        break
    D=[0]*(N+1)
    for i,d in enumerate(A):
        left=max(0,i-d)
        right= min(N-1,i+d)
        D[left]+=1
        D[right+1]-=1
    for i in range(N):
        D[i+1]+=D[i]
    A= D[:-1]

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

Solution (Python):
def Next(a):
    global n
    print(a)
    hajimari=[0]*n
    owari=[0]*n
    for i in range(n):
        hidari=i-a[i]-1
        migi=i+a[i]+1
        if(hidari>=0):
            hajimari[hidari]+=1
        if(migi<n):
            owari[migi]+=1
    print(hajimari)
    print(owari)
    for i in range(n-1):
        hajimari[n-i-2]+=hajimari[n-i-1]
    for i in range(n-1):
        owari[i+1]+=owari[i]
    print(hajimari)
    print(owari)

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

k=min(300,k)

for i in range(k):
    
    hajimari=[0]*n
    owari=[0]*n
    for i in range(n):
        hidari=i-a[i]-1
        migi=i+a[i]+1
        if(hidari>=0):
            hajimari[hidari]+=1
        if(migi<n):
            owari[migi]+=1
    
    
    for i in range(n-1):
        hajimari[n-i-2]+=hajimari[n-i-1]
    for i in range(n-1):
        owari[i+1]+=owari[i]
    
    
    for i in range(n):
        a[i]=n-hajimari[i]-owari[i]

s=[]
for i in range(n):
    s.append(str(a[i]))

print(" ".join(s))

Solution (Python):
import collections
n,k = map(int, raw_input().split(' '))
ais = map(int ,raw_input().split(' '))

prev = ais[::]
for _ in range(k):

	h = collections.Counter()
	for i,d in enumerate(ais):
		u = i+1
		h[max(1, u - d)] += 1
		h[u + d + 1] -= 1

	cumul = 0
	for u in range(1, n+1):
		cumul += h[u]
		ais[u - 1] = cumul
	if prev == ais[::]:
		break
	prev = ais[::]


for e in ais:print e,

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

for i in range(k):
    b = [0]*(n+1)
    for i in range(n):
        if a[i]:
            b[max(0,i-a[i])] += 1
            b[i] -= 1
            b[i+1] += 1 
            b[min(n,i+a[i]+1)] -= 1
    b[0] += 1
    count = b[0]
    for i in range(1,n):
        b[i] += b[i-1]
        count += b[i]
    a = b[:n]
    if count == n*n:
        print(*a)
        exit()
print(*a)

Solution (Python):
from copy import copy
n, k = map(int, input().split())
ns = list(map(int, input().split()))
for i in range(k):
    imosur = [0] * n
    imosul = [0] * n
    ans = [0] * n
    for i in range(n):
        imosur[i] += 1
        if i + ns[i] + 1 < n:
            imosur[i + ns[i] + 1] -= 1
        imosul[n - i - 1] += 1
        if n - i - 2 - ns[n - i - 1] >= 0:
            imosul[n - i - 2- ns[n - i -1]] -= 1
    r=0
    l=0
    for i in range(n):
        r += imosur[i]
        ans[i] += r
        l += imosul[n - i - 1]
        ans[n - i - 1] += l - 1
    if min(ans) == n:
        print(*[n for _ in range(n)])
        exit()
    ns = copy(ans)
print(*ans)

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

if K > 40:
  print(*[N for _ in range(N)])
  quit()

def f(A):
    table = [0]*(N+1)
    for i, v in enumerate(A):
        d = A[i]
        table[max(0, i-d)] += 1
        table[min(N, i+d+1)] -= 1

    cumsum = [table[0]]
    for i in range(1, N):
        cumsum.append(cumsum[-1]+table[i])
    return cumsum

for i in range(K):
    A = f(A)
print(*A)

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

for i in range(K):
    P = [0 for _ in range(N)] + [0]
    for j in range(N):
        P[max(0, j - A[j])] += 1
        P[min(N, j + A[j] + 1)] -= 1
    A = [0 for _ in range(N)]
    for j in range(N):
        P[j + 1] += P[j]
    flag = False
    for j in range(N):
        A[j] = P[j]
        if A[j] < N:
            flag = True
    if not flag:
        break

print(*A)

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

i = 0
for _ in range(min(K, 50)):
    B = [0] * (N + 1)
    for i, a in enumerate(A):
        j = max(0, i - a)
        B[j] += 1
        j = min(N, i + a + 1)
        B[j] -= 1
    B.pop()
    A = list(accumulate(B))

print(*A)

Solution (Python):
import copy
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(min(100,k)):
  L1=[0]*(n+2)
  if i!=0:
    a=L2[1:n+1]
  for j in range(n):
    L1[max(j-a[j],0)]+=1
    L1[min(j+a[j],n)+1]-=1
  L2=[0]
  for i in range(n+2):
    L2.append(L2[-1]+L1[i])
a=L2[1:n+1]
for i in range(len(a)):
  a[i]=str(a[i])
print(' '.join(a))

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

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


def print_ans(ans):
   ans = list(map(lambda x: str(x) if x <= n else str(n), ans))
   print(" ".join(ans))

all_max = [n] * n
if k > 50:
   print_ans(all_max)
   exit()



for _ in range(k):
   pre_a = a[:]
   imos = [0 for _ in range(n+1)]
   for i in range(n):
      l = max(0, i - pre_a[i])
      r = min(n, i + pre_a[i] + 1)
      imos[l] += 1
      imos[r] -= 1
   
   v = 0
   for i in range(n):
      v += imos[i]
      if v > n:
         v = n
      a[i] = v
print_ans(a)

Solution (Python):

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

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



cnt = 0

while cnt < k:
    imos = [0] * (n + 1)
    for i in range(n):
        imos[max(i - a[i], 0)] += 1
        imos[min(i + a[i] + 1, n)] -= 1
    for i in range(n):
        imos[i + 1] += imos[i]
    a = imos[0:n]
    cnt += 1
    if min(a) == n:
        break
print(*a)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(k):
    accu = [0]*(n+1)
    for i in range(n):
        accu[max(i-a[i], 0)] += 1
        accu[min(i+a[i]+1, n)] -= 1
    now = 0
    for i in range(n):
        now += accu[i]
        a[i] = now
    if sum(a)==n*n:
        break
print(*a)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = A.copy()
k = 0
while k < K and sum(B) < N**2:
  tmp = [0]*N
  i = 0
  while i < N:
    a = B[i]
    tmp[max(0, i-a)] += 1
    if i+a+1 < N:
      tmp[i+a+1] -= 1
    i += 1
  s = 0
  i = 0
  while i < N:
    B[i] = tmp[i]+s
    s = B[i]
    i += 1
  k += 1
print(" ".join([str(b) for b in B]))

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

K = min(100, K)

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

    for j in range(1, N):
        B[j] += B[j - 1]
    A = B[:-1]

print(*A)

Solution (Python):

from sys import stdin
input = stdin.readline
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
a = inl()
for kk in range(k):
    l = [0]*n
    r = [0]*(n+1)
    for j in range(n):
        l[max(0,j-a[j])] += 1
        r[min(n,j+a[j]+1)] += 1
    cnt = 0
    mn = BIG
    for j in range(n):
        cnt += l[j]-r[j]
        a[j] = cnt
        mn = min(mn,cnt)
    if mn==n:
        break
pad = ''
for j in range(n):
    printn(pad+str(a[j]))
    pad = ' '
print('')

Solution (Python):
N, K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(K):
    B = [0] * N
    for j in range(N):
        if A[j] == 0:
            continue
        if j - A[j] < 0:
            B[0] += 1
        else:
            B[j - A[j]] += 1
        B[j] -= 1
        if j + 1 <= N-1:
            B[j + 1] += 1
        if j + A[j] + 1 <= N-1:
            B[j + A[j] + 1] -= 1
    
    for j in range(N-1):
        B[j+1] += B[j]
        B[j] += 1
    B[-1] += 1
    
    A = B[:]
    
    if all([i == N for i in A]):
        break

print(*A)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def main():
    N,K = map(int,input().split())
    a = [0] + list(map(int,input().split())) + [0]
    
    for i in range(K):
        imos = [0]*(N+2)
        for j in range(1,N+1):
            num = a[j]
            imos[max(j-num,0)] += 1
            imos[min(j+num+1,N+1)] -= 1
        for j in range(N+1):
            imos[j+1] = imos[j]+imos[j+1]
        imos[0] = 0
        a = imos
        if sum(a[1:N+1]) == N**2:
            break
    
    print(*a[1:N+1])

if __name__ == "__main__":
    main()

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(min(K,41)):
    l=[0]*(N+1)
    c=0
    for j in range(N):
        if j-A[j]>0:
            l[j-A[j]]+=1
        else:
            c+=1
        if A[j]+j<N:
            l[A[j]+j+1]-=1 
    for j in range(N):
        c+=l[j]
        A[j]=c
print(*A)

Solution (Python):

import sys
input = sys.stdin.readline
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n,k = ip()
x = ip()
for _ in range(k):
    dp = [0]*(n+1)
    for i in range(n):
        pos1 = max(i-x[i],0)
        pos2 = min(i+x[i]+1,n)
        dp[pos1] += 1
        dp[pos2] -= 1
    for i in range(1,n+1):
        dp[i] += dp[i-1]
    if x == dp:
        break
    x = list(dp)
print(*x[:-1])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, floor
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


N, K = MAP()
A = LIST()

cnt = 0
while 1:
	a = [0]*(N+1)
	flg = 1
	for i in range(N):
		a[max(0, i-A[i])] += 1
		a[min(N, i+A[i]+1)] -= 1
		if max(0, i-A[i]) == 0 and min(N, i+A[i]+1) == N:
			flg *= 1
		else:
			flg *= 0
	A = list(accumulate(a))
	cnt += 1
	if cnt == K:
		print(*A[:-1])
		exit()
	if flg:
		break

A = [N]*N
print(*A)

Solution (Python):
if __name__ == '__main__':
    from sys import stdin
    
    
    
    import copy
    
    
    
    input = stdin.readline

    n, k = map(int, input().split())
    aa = list(map(int, input().split()))
    
    
    
    
    if k >= 50:
        str_n = str(n)
        ans = [str_n]*n
        print(' '.join(ans))
        exit()
    copy_aa = copy.deepcopy(aa)
    next = [0]*n  
    for _ in range(k):
        calculation_list = [0]*(n+1)
        for index, a in enumerate(copy_aa):
            section_min = index-a if index-a>=0 else 0
            section_max = index+a+1 if index+a+1<=n else n
            calculation_list[section_min] += 1
            
            calculation_list[section_max] -= 1
        now = 0
        for index, calculation in enumerate(calculation_list[:-1]):
            now += calculation
            copy_aa[index] = now
        
        
    print(' '.join(map(str, copy_aa)))

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

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

print(*a)

Solution (Python):
from __future__ import print_function
import sys


if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve(a):
    for j in range(k):
        el = [0] * n
        er = [0] * n
        for i in range(n):
            el[max(i - a[i], 0)] += 1
            er[min(i + a[i], n-1)] += 1
        a = [0]*n
        a[0] = el[0]
        all_n = True
        for i in range(1, n):
            a[i] = a[i-1] + el[i] - er[i-1]
            all_n &= a[i] == n
        if all_n:
            print(*a)
            return
    print(*a)
    return







n, k = RA()
a = RA()
solve(a)

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    key = 50
    nn = n
    while nn > 0:
        key += 1
        nn //= 2
    
    for _ in range(min([key, k])):
        b = [0]*n
        for i in range(n):
            l, r = max([i-a[i], 0]), min([i+a[i], n-1])
            b[l] += 1
            if r != n-1:
                b[r+1] -= 1
        for i in range(n):
            a[i] = 0
            a[i] += b[i]
            if i != 0:
                 a[i] += a[i-1]
    print(*a)

if __name__ == "__main__":
    main()

Solution (Python):

 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
for _ in range(k):
    lst = [0]*(n+1)
    for i in range(n):
        lst[max(i - a[i], 0)] += 1
        lst[min(i + a[i] + 1, n)] -= 1
    a = list(accumulate(lst))[:-1]
    for i in range(n):
        if a[i] != n:
            break
    else:
        print(*a)
        quit()
print(*a)

Solution (Python):
from itertools import accumulate as ac
import copy
n, k = map(int, input().split())
A = list(map(int, input().split()))

def one_term(lis):
    imos = [0] * n

    for i, a in enumerate(lis):
        left = max(0, i - a)
        right = min(n, i + a + 1)
        imos[left] += 1
        try:
            imos[right] -= 1
        except:
            pass
    return list(ac(imos))

ans = A
for i in range(k):
    ans = one_term(ans)
    if ans.count(n) == n:
        break
print(*ans, sep=" ")

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys

INF = 10 ** 17
MOD = 1000000007

from fractions import *
def inverse(f):
    
    return 1/f

def make_next(n, nums):
    imos = [0 for i in range(n)]
    for i, num in enumerate(nums):
        if num > i:
            imos[0] += 1
        else:
            imos[i - num] += 1

        if i + num + 1 < n:
            imos[i+num+1] -= 1
    
    nx = []
    tmp = 0
    for im in imos:
        tmp += im
        nx.append(tmp)

    return nx

def mantan_check(n, nums):
    if sum(nums) == n ** 2:
        return True
    else:
        return False

def solve():
    n, k = getList()
    nums = getList()
    for i in range(k):
        nums = make_next(n, nums)
        if mantan_check(n, nums):
            print(*nums)
            return

    print(*nums)
    return



def main():
    
    
    solve()
if __name__ == "__main__":
    solve()

"""
5 10000000000000
4 0 0 0 0
"""

Solution (Python):
def examA():
    S = SI()
    ans = S[:3]
    print(ans)
    return

def examB():
    A, V = LI()
    B, W = LI()
    T = I()
    L = abs(A-B)
    v = V-W
    if v*T>=L:
        ans = "YES"
    else:
        ans = "NO"
    print(ans)
    return

def examC():
    N, K = LI()
    A = LI()
    for _ in range(min(60,K)):
        cur = N
        L = [0] * (N + 1)
        R = [0] * (N + 1)
        for i in range(N):
            a = A[i]
            if 0<i-a:
                L[i-a] += 1
            else:
                L[0] += 1
            if N>i+a+1:
                R[i+a+1] += 1
            else:
                R[N] += 1
            if cur>a:
                cur = a
        if cur==N:
            break
        A[0] = L[0]
        for i in range(1,N):
            A[i] = A[i-1]+L[i]-R[i]


    print(" ".join(map(str,A)))
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):


import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, A: "List[int]"):
    
    for _ in range(K):
        inc = [0] * N
        dec = [0] * N
        for i in range(N):
            s = max(0, i - A[i])
            e = min(N - 1, i + A[i])
            inc[s] += 1
            dec[e] += 1
        nexts = []
        cur = 0
        found = False
        for i in range(N):
            cur += inc[i]
            if cur < N:
                found = True
            nexts.append(cur)
            cur -= dec[i]
        A = nexts
        if not found:
            break
    print(*A, sep=' ')
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, K, A)

if __name__ == '__main__':
    main()

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
for k in range(K):
    imos = [0] * (N+1)
    for i,a in enumerate(A):
        l = max(0, i-a)
        r = min(N, i+1+a)
        imos[l] += 1
        imos[r] -= 1
    imos[0] = min(N, imos[0])
    for i in range(N):
        imos[i+1] = min(N, imos[i] + imos[i+1])
    A = imos[:-1]
    if all(a==N for a in A):
        break
print(*A)

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

for _ in range(k):
    lst = [0] * n
    for i in range(n):
        num = a[i]
        if i-num >= 0:
            lst[i-num] += 1
        else:
            lst[0] += 1
        if i+num+1 <= n-1:
            lst[i+num+1] -= 1
    mini = lst[0]
    for i in range(1, n):
        lst[i] += lst[i-1]
        mini = min(mini, lst[i])
    a = lst[:]
    if mini == n:
        break
print(' '.join(map(str, a)))

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k):
    b=[0]*(n+1)
    for i in range(n):
        b[max(i-a[i],0)]+=1
        b[min(i+a[i]+1,n)]-=1
    for i in range(n):
        b[i+1]+=b[i]
    f=1
    for j in range(n):
        if b[j]!=n:
            f=0
            break
    if f:
        print(*b[:n])
        exit()
    a=b[:]
print(*a[:n])

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

count=0
while True and K>count:
    nx=[0]*N
    for i in range(N):
        posl=max(0,i-A[i])
        posr=min(N-1,i+A[i])
        if N-1>posr:
            nx[posl]+=1
            nx[posr+1]-=1
        else:
            nx[posl]+=1
    for i in range(1,N):
        nx[i]+=nx[i-1]
    A=nx
    count+=1
    if min(A)==N:
        break

print(*A)

Solution (Python):
n,k=[int(j)for j in input().split()]
a=[int(j)for j in input().split()]
if n<=k:
    print(*[n]*n)
    exit()
import copy
for idx in range(k):
    table=[0]*n
    for i in range(n):
        table[max(i-a[i],0)]+=1
        if i+a[i]+1<n:
            table[i+a[i]+1]-=1
    for i in range(1,n):
        table[i]+=table[i-1]
    a=copy.deepcopy(table)
    if a==[n]*n:
        break
print(*a)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(K):
    d=[0]*(N+1)
    for j,a in enumerate(A):
        d[max(0,j-a)]+=1
        d[min(N,j+a+1)]-=1
    b=1
    for j in range(N):
        if d[j]!=N:
            b=0
        d[j+1]+=d[j]
    A=d[:-1]
    if b>0:
        break
print(*A)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
import copy
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))


def main():
	N, K = getlist()
	A = getlist()
	if K >= 40:
		ans = [N] * N
		print(*ans)
		return

	for i in range(K):
		imos = [0] * (N + 1)
		for j in range(N):
			left = max(0, j - A[j])
			right = min(N, j + A[j] + 1)
			imos[left] += 1
			imos[right] -= 1

		for j in range(N):
			imos[j + 1] += imos[j]

		A = copy.deepcopy(imos[:-1])

	print(*A)

if __name__ == '__main__':
	main()

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0 for i in range(n+1)]
b.append(0)
for i in range(k):
    for j in range(n):
        if a[j] > j and a[j] + j + 1 > n:
            b[0] += 1
            b[-1] -= 1
        if a[j] > j and a[j] + j + 1 <= n:
            b[0] += 1
            b[j+a[j]+1] -= 1
        if a[j] <= j and a[j] + j + 1 > n:
            b[j-a[j]] += 1
            b[-1] -= 1
        if a[j] <= j and a[j] + j + 1 <= n:
            b[j-a[j]] += 1
            b[j+a[j]+1] -= 1
    for j in range(1,n):
        b[j] += b[j-1]
    for j in range(n):
        a[j] = b[j]
    if b.count(n) == n:
        break
    for j in range(n):
        a[j] = b[j]
    b = [0 for i in range(n+1)]
print(*a)