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):
n, k = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(min(50, k)):
    l = [0]*(n+1)
    for i in range(n):
        l[max(i-a[i], 0)] += 1 
        l[min(i+a[i]+1, n)] -= 1 
    add = 0
    for i in range(n):
        add += l[i] 
        a[i] = add
print(*a)

Solution (Python):
import sys
import numpy as np
from numba import njit

read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline

@njit('(i8[::1]),',cache=True)
def update(A):
    N=len(A)
    B=np.zeros_like(A)
    for i,x in enumerate(A):
        l=max(0,i-x)
        r=min(N-1,i+x)
        B[l]+=1
        if r+1<N:
            B[r+1]-=1
    B=np.cumsum(B)
    return B

N,K=map(int,input().split())
A=np.array(input().split(),np.int64)
K=min(K,100)
for _ in range(K):
    A=update(A)
print(" ".join(A.astype(str)))

Solution (Python):




    

    
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))       
l =0
r =N

if N <=K:
    A=[N]*N

else:
    for j in range(K):
        B =[0]*(N+1)
        for i in range(N):
            index =A[i]
            l =max(i -index,0)
            r =min(i +index +1,N) 
            B[l] +=1 
            B[r] -=1
        
        from itertools import accumulate
        del B[-1]
        A =list(accumulate(B))
        if sum(A) ==N*N:
            print(*A)
            sys.exit(0)
    
print(*A)

Solution (Python):
import numpy as np


def solve(N, K, A):
    E = np.arange(0, N)
    for _ in range(K):
        B = np.zeros(N + 1, dtype=np.int64)
        np.add.at(B, np.maximum(0, E - A), 1)
        np.add.at(B, np.minimum(E + A + 1, N), -1)
        A = np.cumsum(B)[:-1]
        if np.all(A == N):
            return A
    return A


N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
print(' '.join(map(str, solve(N, K, A))))

Solution (Python):
import numpy as np
from numba import njit


@njit('i8[:](i8,i8,i8[:])')
def solve(N, K, A):
    E = np.arange(0, N)
    for _ in range(K):
        B = np.zeros(N + 1, dtype=np.int64)
        for i_l, i_r in zip(np.maximum(0, E - A), np.minimum(E + A + 1, N)):
            B[i_l] += 1
            B[i_r] -= 1
        A = np.cumsum(B)[:-1]
        if np.all(A == N):
            return A
    return A


N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
print(' '.join(map(str, solve(N, K, A))))

Solution (Python):
import math
n,k=map(int,input().split())
  
a=[0]*n
ans=[0]*n
a=list(map(int,input().split()))
check=math.ceil(math.log2(n))+1
if (k>=42):
  a=[n]*n
  print(" ".join(map(str,a)))
else:
  for _ in range(k):
    ans=[0]*n
    table=[0]*n
    for i in range(n):
      left=max(0,i-a[i])
      right=min(n-1,i+a[i])
      table[left]+=1
      if (right+1<n):
        table[right+1]-=1
      
      
      
    
    for i in range(1,n):
      table[i]+=table[i-1]
    a=table
 
  print(" ".join(map(str,a)))

Solution (Python):
import numpy as np
from numba import njit
import itertools

@njit
def imos(N,K,A):

    
    B=np.zeros((N+1),dtype=np.int64)
    
    for i in range(N):
        a=A[i]
        start=max(0,i-a)
        end=min(N,i+a+1)
        B[start]+=1
        B[end]-=1
        
    return np.cumsum(B)[:N]
    

if __name__=="__main__":
    N,K=map(int, input().split())
    A=list(map(int, input().split()))
    for _ in range(K):
        A=imos(N,K,A)
        if A.min()==N:
            break   
    
    print(*A)

Solution (Python):



    

    
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))
    
    
l =0
r =N
cumulative_sum =[0]*N

if N <=K:
    A=[N]*N

else:
    for j in range(K):
        B =[0]*(N+1)
        for i in range(N):
            index =A[i]
            if i-index <0:
                l=0
            else:
                l =i -index
            if i +index +1 >=N:
                r =N 
            else:
                r =i +index +1
            B[l] +=1 
            B[r] -=1
        
        from itertools import accumulate
        del B[-1]
        A =list(accumulate(B))
        if sum(A) ==N*N:
            print(*A)
            sys.exit(0)
    
print(*A)

Solution (Python):
import math
N, K = map(int, input().split())
lightPow = list(map(int, input().split()))

for i in range(K):
  newLightPow = [0]*(N+1)
  
  for pos in range(1, N+1):
    low = pos - lightPow[pos-1]
    high = pos + lightPow[pos-1]
    low = min(max(1, low), N)
    high = min(max(1, high), N)
    newLightPow[low-1] += 1
    newLightPow[high] -= 1
    
    
    
    
  check = True
  for i in range(0, N):
    if (i > 0):
      newLightPow[i] += newLightPow[i-1]
    if (newLightPow[i] < N):
      check = False
  lightPow = newLightPow
  if (check):
    break

print(*lightPow[:-1])

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

for t in range(k):
      ok=True
      b=[0]*n
      for i in range(n):
            left=max(0,i-a[i])
            b[left]+=1
            if i+a[i]+1 <= n-1:
                  right=i+a[i]+1
                  b[right]-=1
      for i in range(1,n):
            b[i]=b[i-1]+b[i]
      for i in range(n):
            if a[i]!=b[i]:
                  ok=False
            a[i]=b[i]
      if ok==True:
            break

print(*a)

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

Solution (Python):
import numpy as np
from numba import njit


@njit('i8[:](i8,i8,i8[:])')
def solve(N, K, A):
    for _ in range(K):
        B = np.zeros(N + 1, dtype=np.int64)
        for i in range(N):
            a = A[i]
            B[max(0, i - a)] += 1
            B[min(N, i + a + 1)] -= 1
        A = np.cumsum(B)[:-1]
        if np.all(A == N):
            return A
    return A


N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
print(' '.join(map(str, solve(N, K, A))))

Solution (Python):

import math
n,k=map(int,input().split())
A=list(map(int,input().split()))
kukan=[]
ans=[0]*n
for i in range(k):
    B=[0]*(n+1)
    for j in range(n):
        l=max(0,j-A[j])
        r=min(j+A[j]+1,n)
        
        B[l]+=1
        B[r]-=1
    for j in range(n):
        B[j+1]+=B[j]
    B.pop()
    if A==B:
        break
    A=B
for b in B:
    print(b)

Solution (Python):
from itertools import accumulate

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


for _ in range(K):
    lamp = [0] * (N + 1)                    
                                            
                                            
    for i, a in enumerate(A):
        lamp[max(i-a,0)] += 1
        lamp[min(i+a+1,N)] -=1
    B = tuple(accumulate(lamp))[:-1]
    if B == A:
        break
    A = B


print(*A)

Solution (Python):
import copy
n,k,*A = map(int,open(0).read().split())
for _ in range(min(50,k)):
    B = [0] * (n+1)
    for i,d in enumerate(A):
        start = max(0,i-d)
        B[start] += 1
        end = min(n,i+d+1)
        B[end] -= 1
    light = 0 
    for i,b in enumerate(B[:n]):
        light += b
        A[i] = light

print(*A)

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

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

for x in range(K):

	raise_data = [0] * (N + 1)
	for i, d in enumerate(data):
		raise_data[max(0, i - d)] += 1
		raise_data[min(N, i + d + 1)] -= 1
	
	height = 0
	ended = 0
	for i in range(N):
		height += raise_data[i]
		data[i] = height
		if height == N:
			ended += 1
	
	if ended == N:

		break
	
print(*data)

Solution (Python):
import numpy as np
from numba import njit

@njit
def update(a):
  n = len(a)
  b = np.zeros_like(a)
  for i,x in enumerate(a):
    l = max(0, i-x)
    r = min(n-1, i+x)
    b[l] += 1
    if r+1 < n:
      b[r+1] -= 1
  b = np.cumsum(b)
  return b

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

for _ in range(k):
  a = update(a)
  if np.all(a==n):
    break
    
print(' '.join(map(str, a)))

Solution (Python):
import sys
from numba import njit

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

@njit(cache=True)
def solve(n, k, a):
    if k == 0:
        return a
    b = [0]*n
    for _ in range(k):
        for i in range(n):
            if i > a[i]:
                b[i-a[i]] += 1
            else:
                b[0] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        for i in range(n-1):
            b[i+1] += b[i]
            a[i] = 0
        a[-1] = 0
        b, a = a, b
        if min(a) >= n:
            break
    return a

solve(0, 0, [0, 1, 2])
n, k = nm()
a = nl()
print(*solve(n, k, a))

Solution (Python):

from itertools import*
n, k, *A = map(int, open(0).read().split())

def imos(l, r):
    B[l] += 1
    if r + 1 != n:
        B[r + 1] -= 1

for _ in [0] * min(k, 41):
    B = [0] * n
    for i, a in enumerate(A):
        imos(max(i - a, 0), min(i + a, n - 1))
    *A, = accumulate(B)
print(*A)

Solution (Python):
import sys
from itertools import accumulate
from numba import njit

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

@njit
def solve(n, k, a):
    b = [0]*n
    for _ in range(k):
        for i in range(n):
            if i > a[i]:
                b[i-a[i]] += 1
            else:
                b[0] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        for i in range(n-1):
            b[i+1] += b[i]
            a[i] = 0
        a[-1] = 0
        b, a = a, b
        if min(a) >= n:
            break
    return a

n, k = nm()
a = nl()
print(*solve(n, k, a))

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))
for i in range(k):
  C = [0]*(n+1)
  for j in range(n):
    C[max(0, j-A[j])] += 1
    C[min(n-1, j+A[j])+1] -= 1
  v = 1
  for j in range(n):
    C[j+1]=C[j+1]+C[j]
    if C[j]!=n:
      v = 0
  if v:
    break
  A = C
C = [str(c) for c in C[:-1]]
print(' '.join(C))

Solution (Python):
import numpy as np
from numba import njit

@njit
def update(a):
  n = len(a)
  b = np.zeros_like(a)
  for i,x in enumerate(a):
    l = max(0, i-x)
    r = min(n-1, i+x)
    b[l] += 1
    if r+1 < n:
      b[r+1] -=1
  b = np.cumsum(b)
  return b

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

k = min(k, 100)

for _ in range(k):
  a = update(a)
print(' '.join(map(str,a)))

Solution (Python):
import numpy as np
from numba import njit
@njit
def op(A, n):
    B = np.zeros_like(A)
    for i, a in enumerate(A[:n]):
        B[max(i - a, 0)] += 1
        B[min(n - 1, a + i) + 1] -= 1
    return np.cumsum(B)

def main():
    n, k = list(map(int, input().split()))
    A = np.array(list(map(int, input().split())) + [0, ], dtype = np.int)
    for _ in range(k):
        A_new = op(A, n)
        if all(A[:n] == A_new[:n]):
            break
        A = A_new
    print(' '.join(list(map(str, A[:n]))))

if __name__ == '__main__':
    main()

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

for i in range(min(k, 450)):
    tmp = [0] * (n + 1)
    for j in range(n):
        tmp[max(0, j - a[j])] += 1
        tmp[min(n, j + a[j] + 1)] -= 1
    
    cnt = 0
    for j in range(n):
        cnt += tmp[j]
        a[j] = cnt

for i in range(n):
    print(a[i], end=' ')

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):
import copy

def check(arr, val):
    for i in arr:
        if not i == val:
            return False
    return True

n, k = map(int, input().split())
a = [int(_) for _ in input().split()]

for _ in range(k):
    aa = [0] * n
    for i in range(n):
        aa[max(0, i-a[i])] += 1
        r = i+a[i]+1
        if r < n:
            aa[r] -= 1
    for i in range(1, n):
        aa[i] += aa[i-1]
    a = aa.copy()
    if check(a, n):
        break

for i in a:
    print(i, end=' ')
print()

Solution (Python):
import sys
import numpy as np
from numba import njit
 
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit
def update(A):
  N = len(A)
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    l = max(0, i-x)
    r = min(N-1, i+x)
    B[l] += 1
    if r + 1 < N:
      B[r+1] -= 1
  B = np.cumsum(B)
  return B
    
    
N,K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
  A = update(A)
print(' '.join(A.astype(str)))

Solution (Python):
import sys
import numpy as np
from numba import njit
 
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit('(i8[::1],)', cache=True)
def update(A):
  N = len(A)
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    l = max(0, i-x)
    r = min(N-1, i+x)
    B[l] += 1
    if r + 1 < N:
      B[r+1] -= 1
  B = np.cumsum(B)
  return B
    
    
N,K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
  A = update(A)
print(' '.join(A.astype(str)))

Solution (Python):
import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B
 
N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))
for i in range(k):
  C = [0]*(n+1)
  for j in range(n):
    p = max(0, j-A[j])
    q = min(n-1, j+A[j])
    C[p] += 1
    C[q+1] -= 1
  v = 1
  for j in range(n):
    C[j+1]=C[j+1]+C[j]
    if C[j]!=n:
      v = 0
  if v:
    break
  A = C
C = [str(c) for c in C[:-1]]
print(' '.join(C))

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
si = [0 for i in range(n+1)]
p = [1 for i in range(n)]
import copy 
for q in range(min(k,50)):
    v = 0
    s = copy.deepcopy(si)
    for i in range(n):
        if a[i] != 0:
            s[max(i-a[i],0)] += 1
            s[min(i+a[i]+1,n)] -= 1
            a[i] = 0
        else:
            a[i] = 1
    for i in range(n):
        v += s[i]
        a[i] += v
for i in range(n):
    print(a[i], end = ' ')

Solution (Python):
n,k,*l=map(int,open(0).read().split())
for _ in range(min(k,41)):
  s=[0]*-~n
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  for i in range(n): s[i+1]+=s[i]
  l=s
print(*l[:n])

Solution (Python):
import itertools
n,k=map(int,input().split())
l=list(map(int,input().split()))
if k>42:
    l=[n]*n
    print(*l)
else:
    for _ in range(k):
        countl=[0]*(n+1)
        for i in range(n):
            countl[max(1,i+1-l[i])]+=1
            if i+2+l[i]<=n:
                countl[i+2+l[i]]-=1
            
        l=list(itertools.accumulate(countl))
        l.remove(l[0])
    print(*l)

Solution (Python):
n,k,*l=map(int,open(0).read().split())
for _ in range(k):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  for i in range(n):
    s[i+1]+=s[i]
  s.pop()
  if s==l: break
  l=s
print(*l)

Solution (Python):
import numpy as np
from numba import njit, prange


N, K = map(int, input().split())
As = list(map(int, input().split()))
'''
N = 200000
K = 100000
As = [0] * N


@njit("i8[:](i8[:],)", cache = True)
def update(A_array):
    before_csum = np.zeros(N+1, np.int64)
    for i, A in enumerate(A_array[:N]):
        before_csum[max(0, i-A)] += 1
        before_csum[min(N, i+A+1)] -= 1
    return np.cumsum(before_csum)
    
A_array = np.array(As + [0], dtype = np.int64)
for k in range(min(K, 50)):
    A_array = update(A_array)
    
print(*A_array.tolist()[:N])

Solution (Python):
import numpy as np
from numba import jit
N,K=map(int,input().split())
A=list(map(int,input().split()))

@jit
def imos(A):
    B=np.zeros_like(A)
    for i,x in enumerate(A):
        a=max(0,i-x)
        b=min(i+x,N-1)
        B[a]+=1
        if b+1<=N-1:
            B[b+1]-=1
    B=np.cumsum(B)
    return B

for i in range(K):
    if i>=50:
        break
    A=imos(A)
print(*A)

Solution (Python):
import numpy as np
from numba import jit
@jit(cache = True)
def solve(n,k,A):
    l,r=0,0
    for i in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for x,y in enumerate(list(A)):
            l=max(0,x-y)
            r=min(n,x+y+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        if A[A==n].size==n:
            break
    return A
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=np.array(a)
X=solve(n,k,A)
print(*X,sep=' ')

Solution (Python):
import numpy as np
from numba import njit


N, K = map(int, input().split())
As = list(map(int, input().split()))
'''
N = 200000
K = 100000
As = [0] * N


@njit(cache = True)
def update(A_array):
    before_csum = np.zeros(N+1, np.int32)
    for i, A in enumerate(A_array[:N]):
        before_csum[max(0, i-A)] += 1
        before_csum[min(N, i+A+1)] -= 1
    return np.cumsum(before_csum)
    
A_array = np.array(As + [0], dtype = np.int32)
for k in range(min(K, 50)):
    A_array = update(A_array)
    
print(*A_array.tolist()[:N])

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
tu=0
td=0
if k>=40:
  a=[n]*n
else:
  for j in range(k):
    temp=[0]*n
    for i in range(n):
      td=max(i+1-a[i],1)
      temp[td-1]=temp[td-1]+1
      tu=min(i+1+a[i],n)
      if tu!=n:
        temp[tu]=temp[tu]-1
    a[0]=temp[0]
    for i in range(1,n):
      a[i]=a[i-1]+temp[i]
L=[str(t) for t in a]
L=" ".join(L)
print(L)

Solution (Python):
import numpy as np
from numba import njit


n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
@njit('(i8[::1]),', cache=True)
def update(a):
    b = np.zeros_like(a)
    for i, x in enumerate(a):
        l = max(0, i - x)
        r = min(n - 1, i + x)
        b[l] += 1
        if r + 1 < n:
            b[r + 1] -= 1
    b = np.cumsum(b)
    return b
k = min(k, 100)
for i in range(k):
    a = update(a)
print(' '.join(a.astype(str)))

Solution (Python):
import numpy as np
from numba import njit


N, K = map(int, input().split())
As = list(map(int, input().split()))
'''
N = 200000
K = 100000
As = [0] * N


@njit()
def update(A_array):
    before_csum = np.zeros(N+1, np.int32)
    for i, A in enumerate(A_array[:N]):
        before_csum[max(0, i-A)] += 1
        before_csum[min(N, i+A+1)] -= 1
    return np.cumsum(before_csum)
    
A_array = np.array(As + [0], dtype = np.int32)
for k in range(min(K, 50)):
    A_array = update(A_array)
    
print(*A_array.tolist()[:N])

Solution (Python):
from itertools import accumulate

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

current_arr = A
if K > 41:
    print(*([N]*N))
    exit()
for _ in range(K):
    imos = [0] * N
    ruiseki = [0] * (N+1)
    for i, ai in enumerate(current_arr):
        imos[max([0, i-ai])] += 1
        if i+ai+1 < N:
            imos[i+ai+1] -= 1
    for j, im in enumerate(imos):
        ruiseki[j+1] = ruiseki[j] + im
    current_arr = ruiseki[1:]



print(*current_arr)

Solution (Python):
from itertools import accumulate
n,k = map(int, input().split())
As = list(map(int, input().split()))
for i in range(k):
    imos = [0] * (n+1)
    for i,a in enumerate(As):
        l = max(0, i-a)
        r = min(n, i+a+1)
        imos[l] += 1
        imos[r] -= 1
    acc = list(accumulate(imos))
    
    if acc[:-1] == As:
        print(*As)
        exit()
    As = acc[:-1]
print(*As)

Solution (Python):
import sys
from itertools import accumulate

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

current_arr = A
if K > 41:
    print(*([N]*N))
else:
    for _ in range(K):
        imos = [0] * N
        ruiseki = [0] * (N+1)
        for i, ai in enumerate(current_arr):
            imos[max([0, i-ai])] += 1
            if i+ai+1 < N:
                imos[i+ai+1] -= 1
        for j, im in enumerate(imos):
            ruiseki[j+1] = ruiseki[j] + im
        current_arr = ruiseki[1:]



    print(*current_arr)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    for x in range(k if k < 50 else 50):
        B = [0] * n
        for j in range(n):
            l = max(0, j - A[j])
            r = min(n - 1, j + A[j])
            B[l] += 1
            if r + 1 < n:
                B[r + 1] -= 1

        for x in range(1, n):
            B[x] += B[x - 1]
        A = B

    print(*A)


if __name__ == '__main__':
    resolve()

Solution (Python):
def action(A, N):
  B = [0] * N
  for i, bright in enumerate(A):
    s = max(0, i - bright)
    B[s] += 1
    e = min(N, i + bright)
    if e < N - 1:
      B[e + 1] -= 1
  
  for i in range(N - 1):
    B[i + 1] += B[i]
  return B

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

  for i in range(K):
    A = action(A, N)
    if (A[0] == N) & all(A):
      break
      
  print(*A, sep=" ")

if __name__ == '__main__':
  main()

Solution (Python):
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
for j in range(min(k, 42)):
    bit = [0 for _ in range(n)]
    for i in range(n):
        bit[max(i - a[i], 0)] += 1
        if i + a[i] + 1 < n:
            bit[i + a[i] + 1] -= 1
    result = [bit[0]]
    for i in range(n - 1):
        result.append(bit[i + 1] + result[-1])
    a = result
print(' '.join(list(map(str, a))))

Solution (Python):
n,k,*l=map(int,open(0).read().split())
for _ in range(k):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  s[0]=min(s[0],n)
  for i in range(1,n):
    s[i]=min(s[i-1]+s[i],n)
  s.pop()
  if s==l: break
  l=s
print(*l)

Solution (Python):
n,k,*l=map(int,open(0).read().split())
for _ in range(k):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  s[0]=min(s[0],n)
  for i in range(1,n):
    s[i]=min(s[i-1]+s[i],n)
  if s==l: break
  l=s
print(*l[:n])

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

Solution (Python):
import numpy as np
from numba import njit


@njit
def solve(N, K, A):
    for _ in range(K):
        B = np.zeros(N + 1, dtype=np.int64)
        for i in range(N):
            a = A[i]
            B[max(0, i - a)] += 1
            B[min(N, i + a + 1)] -= 1
        A = np.cumsum(B)[:-1]
        if np.all(A == N):
            return A
    return A


N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
print(' '.join(map(str, solve(N, K, A))))

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



for _ in range(K):
    new = [0] * N
    imos = [0] * N
    for i, a in enumerate(A):  
        imos[max(0, i-a)] += 1
        if i+a+1 <= N-1:  
            imos[i+a+1] -= 1
    for i in range(N):
        new[i] = new[i-1] + imos[i]
    
    A = new
    if sum(A) == N*N:
        break
print(*A)

Solution (Python):
def draft(A, K, N):
    for _ in range(1, K+1):
        tmp = [0]*(N+1)
        for i in range(N):
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        f = True
        for i in range(N):
            tmp[i+1] += tmp[i]
            A[i] = tmp[i]
            if A[i] != N:
                f = False
        if f:
            break
    for i in range(N):
        print(A[i], end=" ")

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

if __name__ == "__main__":
    main()

Solution (Python):
n,k,*l=map(int,open(0).read().split())
for _ in range(min(k,41)):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  l[0]=min(s[0],n)
  for i in range(1,n):
    l[i]=min(l[i-1]+s[i],n)
print(*l)

Solution (Python):
import sys
from itertools import accumulate

def solve(n,k,a):
    for _ in range(k):
        if a==[n]*n:    return a
        t = [0]*(n+1)
        for i,x in enumerate(a):
            t[max(0,i-x)] += 1
            t[min(n,i+x+1)] -=1
        a = list(accumulate(t))[:-1]
    return a

n,k = map(int,sys.stdin.readline().rstrip().split())
a = list(map(int,sys.stdin.readline().rstrip().split()))

print(*solve(n,k,a))

Solution (Python):
import copy
import sys
import math

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    B = [0] * n

    for i in range(min(k, 41)):
        for j in range(n):
            l = max(0, j-A[j]) 
            r = min(n-1, j+A[j]) 
            B[l] += 1
            if (r+1 < n):
                B[r+1] -= 1 

        for j in range(n-1):
            B[j+1] += B[j]

        A = copy.deepcopy(B)
        B = [0] * n

    print(*A)

if __name__ == '__main__':
    main()

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

@jit
def solve(k,n,a):
    for _ in range(k):
        Y = [0]*(n+1)
        for i, x in enumerate(a):
            Y[max(0, i-x)] += 1
            Y[min(n, i+x+1)] -= 1
        for j in range(1, n):
            Y[j] += Y[j-1]
        if a == Y[:-1]:
            break
        a = Y[:-1]
    return a

ans=solve(K,N,A)
print(*ans)

Solution (Python):
n,k,*l=map(int,open(0).read().split())
for _ in range(min(k,99)):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  l[0]=min(s[0],n)
  for i in range(1,n):
    l[i]=min(l[i-1]+s[i],n)
print(*l)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)

def main():
    N, K = LI()
    A = LI()

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

        if A == B:
            break
        A = B
    print(*A[:-1], sep=" ")


main()

Solution (Python):
import copy
import sys
import math

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    B = [0] * n

    

    for i in range(min(k, 41)):
        for j in range(n):
            l = max(0, j-A[j]) 
            r = min(n-1, j+A[j]) 
            B[l] += 1
            if (r+1 < n):
                B[r+1] -= 1 

        for j in range(n-1):
            B[j+1] += B[j]

        A = copy.deepcopy(B)
        B = [0] * n

    print(*A)

if __name__ == '__main__':
    main()

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

for i in range(K):
    table = [0 for _ in range(N*2)]
    
    for j in range(N):
        ai = As[j]
        
        table[max((j-ai)*2-1, 0)] += 1
        
        table[min((j+ai)*2+1, N*2-1)] -= 1
    
    
    for j in range(N*2):
        if j > 0:
            table[j] += table[j-1]
    
    
    for j in range(N):
        As[j] = table[j*2]
    
    exit_condition = True
    for j in range(N):
        if As[j] != N:
            exit_condition = False
            break
    
    if exit_condition:
        print(*As)
        exit(0)
            

print(*As)

Solution (Python):
import math
import numpy as np

n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]


for _ in range(k):
    new_a = np.zeros(n+1,dtype=int)
    np.add.at(new_a, np.maximum(0,np.arange(0, n)-a), 1)
    np.add.at(new_a, np.minimum(n,np.arange(0, n)+a+1), -1)
    a = new_a.cumsum()[:-1]
    if np.all(a==n):
        break

print(" ".join([str(x) for x in a]))

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

    for _ in range(k):
        imos = [0]*(n+1)
        finish = True
        for i, brightness in enumerate(a):
            if finish and brightness != n:
                finish = False
            begin = max(i - brightness, 0)
            end = i + brightness
            imos[begin] += 1
            if end < n:
                imos[end + 1] -= 1
        if finish:
            break
        for i in range(n-1):
            imos[i+1] += imos[i]
        a = imos[:-1]
    print(*a, sep=" ")


if __name__ == "__main__":
    main()