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,*A=map(int,open(0).read().split())
for _ in range(K):
  B=[0]*(N+1)
  for i,j in enumerate(A):
    B[max(0,i-j)]+=1
    B[min(N,i+j+1)]-=1
  for i in range(N):B[i+1]+=B[i]
  if A==B:break
  A=B
print(*A[:-1])

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

for _ in range(k):
    new_A = [0]*(n+1)
    cnt = 0
    for i in range(n):
        a = A[i]
        if a == n:
            cnt += 1
        L = max(0, i-a)
        R = min(n, i+a+1)
        new_A[L] += 1
        new_A[R] -= 1
    A = list(accumulate(new_A))
    if cnt == n:
        break

print(*A[:-1])

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(K):
        b = [0] * (N+1)
        for j in range(N):
            a = A[j]
            b[max(j-a, 0)] += 1
            b[min(j+a+1, N)] -= 1
        for k in range(1,N+1):
            b[k] += b[k-1]
        b = b[:N]
        if b == A:
            break
        else:
            A = b
    print(*A)

if __name__ == '__main__':
    main()

Solution (Python):
N,K,*A=map(int,open(0).read().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):B[i+1]+=B[i]
  if A==B:break
  A=B
print(*A[:-1])

Solution (Python):
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(1,N):
    B[i]+=B[i-1]
  if A==B:
    break
  A=B[:]
print(*A[:-1])

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


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

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

Solution (Python):
N, K = map(int, input().split())
As = list(map(int, input().split()))
for i in range(K):
  if min(As) == N:
    break
  dBs = [0]*(N+1)
  for i in range(N):
    A = As[i]
    dBs[max(0, i-A)] += 1
    dBs[min(N, i+A+1)] -= 1
  
  Bs = [dBs[0]]
  for i in range(1, N):
    B = Bs[i-1]+dBs[i]
    Bs.append(B)
  As = Bs
print(" ".join(map(str, As)))

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

Solution (Python):
import numpy as np
from numba import jit
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
@jit
def imos(a):
    tmp = np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        tmp[max(0, i - a[i])] += 1
        tmp[min(i + a[i] + 1, n)] -= 1
    tmp = np.cumsum(tmp)
    return tmp[:n]

for j in range(1, min(k+1, 50)):
    a = imos(a)
print(*a)

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

for _ in range(k):
    b=[0]*n
    for i in range(n):
        b[max(0,i-a[i])]+=1
        if i+a[i]<n-1:
            b[i+a[i]+1]-=1    
    f=0
    tmp=0
    for i in range(n):
        tmp+=b[i]
        a[i]=tmp
        if tmp!=n:
            f=1
    if f==0:
        break
print(*a)

Solution (Python):
import sys
import numpy as np
from numba import njit, i8
input = lambda: sys.stdin.readline().rstrip()

@njit(i8[:](i8[:]), cache=True)
def count(a):
    tmp = np.zeros_like(a)
    for index, num in enumerate(a):
        left = max(0, index-num)      
        right = min(len(a)-1, index+num)  
        tmp[left] += 1              
        if right + 1 < len(a):
            tmp[right + 1] -= 1
    tmp = np.cumsum(tmp)
    return tmp

def main():
    n, k = map(int, input().split())
    a = np.array(list(map(int, input().split())))
    for _ in range(k):
        a = count(a)
        if len(set(a)) == 1 and n in set(a):
            print(*a)
            return
    print(*a)

if __name__ == '__main__':
    main()

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 numpy as np
from numba import njit

@njit 
def imos(n, a):
    l=np.zeros((n+1), dtype = np.int64)

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

    return np.cumsum(l)[:n] 

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

for _ in range(k):
    a = imos(n, a)
    if a.min() == n: 
        break

print(*a)

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

@njit 
def imos(n, a):
    
    l=np.zeros((n+1), dtype = np.int64)

    for i in range(n):
        ai = a[i] 
        start = max(0, i - ai) 
        end = min(n, i + ai + 1) 
        l[start] += 1 
        l[end] -= 1
    return np.cumsum(l)[:n] 

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

for _ in range(k):
    a = imos(n, a)
    if a.min() == n: 
        break

print(*a)

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

@njit 

def imos(n, a):
    
    l=np.zeros((n+1), dtype = np.int64)

    for i in range(n):
        ai = a[i] 
        start = max(0, i - ai) 
        end = min(n, i + ai + 1) 
        l[start] += 1 
        l[end] -= 1
    return np.cumsum(l)[:n] 

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

for _ in range(k):
    a = imos(n, a)
    if a.min() == n: 
        break

print(*a)

Solution (Python):
N,K=map(int,input().split())
List = list(map(int, input().split()))
 
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki
 
for i in range(K):
  List = imosu(List,N)
  if List.count(N) == N:
    break
print(*List)

Solution (Python):
N,K=map(int,input().split())
List = list(map(int, input().split()))
 
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki
 
for i in range(K):
  List = imosu(List,N)
  if List.count(N) == N:
    break
print(*List)

Solution (Python):
import itertools

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

for i in range(K):
    TEMP = [0]*(N+1)
    for j in range(N):
        TEMP[max(0,j-A[j])] +=1
        TEMP[min(N,j+A[j]+1)] -=1
    A = list(itertools.accumulate(TEMP))
    if A[0] == N and A[N-1] == N:
        break

A.pop()
print(*A)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
imos = [0]*(N+1)


for k in range(K): 
    if min(A) == N:
        break

    imos = [0]*(N+1)
    for i,a in enumerate(A): 
        imos[max(0, i-a)] += 1
        imos[min(N, i + a + 1)] -= 1
        
    A = [imos[0]]
    for i in range(1,len(imos)-1): 
        A.append(A[i - 1] + imos[i])
        
print(*A, sep=" ")

Solution (Python):
n,k=map(int, input().split())
a=list(map(int, input().split()))
from itertools import accumulate
for _ in range(min(50,k)):
    new=[0]*n
    for i in range(n):
        j=a[i]
        l=max(0,i-j)
        r=min(n-1,i+j)
        new[l]+=1
        if r+1<n:
            new[r+1]-=1
    new=list(accumulate(new))
    a=new
print(*a)

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

@njit 
def imos(n,k,a):
    
    l=np.zeros((n+1),dtype=np.int64)
    for i in range(n):
        ai=a[i]
        start=max(0,i-ai) 
        end=min(n,i+ai+1) 
        l[start]+=1
        l[end]-=1
    return np.cumsum(l)[: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
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from itertools import accumulate

n,k = readints()
a = readints()

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
    a = list(accumulate(b))[:-1]
    if min(a)==n:
        break
printline(a)

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

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

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

def check(lst):
    for i in range(N):
        if lst[i] != N:
            return False
    return True

def move(lst):
    tmp = [0] * (N + 1)
    for i in range(N):
        a = lst[i]
        left = max(0, i - a)
        right = min(N, i + a + 1)
        tmp[left] += 1
        tmp[right] -= 1
    for i in range(N):
        tmp[i + 1] += tmp[i]
    return tmp

for i in range(K):
    A = move(A)
    if check(A):
        
        break

print (*A[:-1])

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

for _ in range(min(k, 100)):
    new_a = [0]*n
    for i in range(n):
        d = a[i]
        new_a[max(i-d, 0)] += 1
        if i+d+1 <= n-1:
            new_a[i+d+1] -= 1
    for i in range(n-1):
        new_a[i+1] += new_a[i]

    a = new_a

print(*a)

Solution (Python):
n,k = map(int,input().split())
li = list(map(int,input().split()))
ans = [0]*(n+1)
tmp = [0]*(n+1)
tmp_sum = []


k = min(k,100)

for kkk in range(k):
    
    for i,l in enumerate(li):
        if l != 0:
            start = max(0,i-l)
            end = min(n,i+l+1)
            
            tmp[start] += 1
            
            tmp[end] -= 1
    
    last = 0
    for t in tmp:
        last = t+last
        tmp_sum.append(last)
    for i,l in enumerate(li):
        if l == 0:
            tmp_sum[i] += 1
    ans = tmp_sum[:n]
    li = tmp_sum[:n]
    tmp = [0]*(n+1)
    tmp_sum = []
    
    
print(*ans)

Solution (Python):
import sys
input=sys.stdin.readline
from itertools import accumulate
def main():
  n,k=map(int,input().split())
  a=list(map(int,input().split()))
  k=k if k<50 else 50
  for _ in range(k):
    b=[0]*(n+1)
    for i in range(n):
      ai=a[i]
      l,r=i-ai,i+ai+1
      l=0 if l<0 else l
      r=n if r>n else r
      b[l]+=1
      b[r]-=1
    b=tuple(accumulate(b))[:-1]
    a=b
    if min(set(b))==n:
      break
  print(*a)
if __name__ == '__main__':
  main()

Solution (Python):


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

b = [0] * n
for kk in range(k):
    l = [i - a[i] for i in range(n)]
    r = [i + a[i] for i in range(n)]
    l.sort()
    r.sort()
    ln = 0
    rn = 0
    for i in range(n):
        while ln < n and l[ln] <= i:
            ln += 1
        while rn < n and r[rn] <  i:
            rn += 1
        b[i] = ln - rn
    a, b = b, a
    if all(v >= n for v in a):
        break

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

Solution (Python):
from sys import stdin






n, k = map(int, input().split())
intensity = list(map(int, stdin.readline().split()))

count = 0
while count < k:
    totsum = 0
    prefs = [0]*n
    zeros = []
    for i in range(n):
        l = i - intensity[i]
        r = i + intensity[i] + 1

        prefs[max(l, 0)] += 1
        if r <= n-1: 
            prefs[r] += -1
            
    for i in range(1, n):
        prefs[i] += prefs[i-1]
        totsum += prefs[i]
    
    if sum(prefs) == n*n:
        print(*prefs)
        exit()
    
    intensity = prefs
    count += 1

print(*prefs)

Solution (Python):
n, k = map(int, input().split())
A = [*map(int, input().split())]
for i in range(k):
    B = [0]*(n+1)
    for j in range(n):
        l = max(0, j - A[j])
        r = min(n, j + A[j] + 1)
        B[l] += 1; B[r] -= 1
    for j in range(n-1): B[j+1] += B[j]
    B.pop()
    if A == B: break
    A = B
print(*A, sep=' ')

Solution (Python):
n, k = map(int, input().split())
A = [*map(int, input().split())]
for i in range(k):
    B = [0]*n
    for j in range(n):
        l = max(0, j-A[j])
        r = j + A[j] + 1
        B[l] += 1
        if r <= n-1: B[r] -= 1
    is_same = True
    for j in range(n-1):
        B[j+1] = B[j+1] + B[j]
        if B[j+1] != n: is_same = False
    if is_same: break
    A = B
print(*B,sep=' ')

Solution (Python):
n,k = map(int,input().split())
A=[*map(int,input().split())]
for i in range(k):
    B = [0]*n
    for j in range(n):
        d = A[j] 
        l = max(0, j-d) 
        r = j+d+1 
        B[l] += 1
        if r <= n-1: B[r] -= 1
    is_same = True
    for j in range(n-1):
        B[j+1] = B[j+1] + B[j]
        if B[j+1] != n: is_same = False
    
    if is_same: break
    A = B

print(*B,sep=' ')

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  for i in range(k):
    nxtl=[0]*n

    
    
    
    
    
    
    

    ff=True
    for j in range(n):
      left=j-l[j]
      if left<0:
        left=0
      else:
        ff=False
      nxtl[left]+=1

      right=j+l[j]+1
      if right<n:
        nxtl[right]-=1
        ff=False

    for i in range(1,n):
      nxtl[i]+=nxtl[i-1]

    if ff:
      return ' '.join(str(x) for x in l)

    l=nxtl

    

  return ' '.join(str(x) for x in l)


print(main())

Solution (Python):
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from itertools import accumulate

    n, k = map(int, readline().split())
    a = [*map(int, readline().split())]
    for _ in range(min(k, 41)):
        memo = [0] * n
        for i, aa in enumerate(a):
            if i > aa:
                memo[i - aa] += 1
            else:
                memo[0] += 1
            j = i - ~ aa
            if j < n:
                memo[j] -= 1
        a = [*accumulate(memo)]
    print(*a)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    memo = [0] * (n + 1)
    for _ in range(k):
        flag = True
        for i, aa in enumerate(a):
            bf = (i - aa if i - aa >= 0 else 0)
            af = (i + aa + 1 if i + aa < n else n)
            memo[bf] += 1
            memo[af] -= 1
        for i in range(n):
            memo[i + 1] += memo[i]
            a[i] = memo[i]
            if a[i] != n:
                flag = False
            memo[i] = 0
        if flag:
            break
    print(*a)


if __name__ == '__main__':
    main()

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

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A, dtype=int)


fin = [N] * N

@njit(cache=True)
def calc_b(a):
    b = np.zeros(N, dtype=np.int64)
    for i, _a in enumerate(a):
        l = max(0, i - _a)
        r = min(N - 1, i + _a)

        
        b[l] += 1
        if r + 1 < N:
            b[r + 1] -= 1

    b = np.cumsum(b)
    
    return b


for k in range(min(K,100)):
    
    a = calc_b(a)
    
    

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

Solution (Python):
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)
    
    from itertools import accumulate

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    check = [n] * n
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        a = list(accumulate(memo))[:-1]
        if a == check:
            break
    print(*a)


if __name__ == '__main__':
    main()

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
R = [N]*N
def update(A):
    b = [0]*N
 
    for i,a in enumerate(A):
        l = max(0,i-a)
        r = min(N-1,i+a)
 
        b[l] += 1
        if r+1 < N:
            b[r+1] -= 1
    
    res = []
    s = 0
    for i in b:
        s += i
        res.append(s)
    return res
 
for _ in range(K):
    A = update(A)
    if A == R:
      break
print(*A)

Solution (Python):
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        for j in range(n):
            memo[j + 1] += memo[j]
        a = memo[:-1]
        if a == [n] * n:
            break
    print(*a)


if __name__ == '__main__':
    main()

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

for i in range(K):
    lis = [0]*(N+1)
    for j in range(N):
        lis[min(N,j+A[j]+1)] -= 1
        lis[max(0,j-A[j])] += 1
    cnt = 0
    for j in range(N):
        cnt += lis[j]
        A[j] = cnt
    cnt2 = 0
    for j in range(len(A)):
        if A[j] == N:
            cnt2 += 1
    if cnt2==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):
    lis = [0] * (N+1)
    for j in range(N):
        lis[min(N,j+A[j]+1)] -= 1
        lis[max(0, j-A[j])] += 1
    cnt = 0
    for j in range(N):
        cnt += lis[j]
        A[j] = cnt

    cnt2 = 0
    for j in range(N):
        if A[j] == N:
            cnt2 += 1
    if cnt2 == N:
        break
    
print(' '.join(map(str,A)))

Solution (Python):
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
    a[0] = b[0]
    for i in range(1, n):
        a[i] = b[i] + a[i - 1]
    if sum(a) == pow(n, 2):
        break
print(*a)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = [int(x) for x in input().strip().split()]
    l = [0] * (N + 1)
    for i, a in enumerate(A):
        l[max(0, i-a)] += 1
        l[min(N, i+a+1)] -= 1
    p = 0
    cumsum = [0] * (N + 1)
    for i in range(N+1):
        p += l[i]
        cumsum[i] = p
    cumsum_ = A + [0]
    for k in range(min(K-1, 50)):
        p = 0
        for i in range(N+1):
            l[max(0, i-cumsum[i])] += 1
            l[min(N, i+cumsum[i]+1)] -= 1
            l[max(0, i-cumsum_[i])] -= 1
            l[min(N, i+cumsum_[i]+1)] += 1

        cumsum_ = cumsum[:]
        for i in range(N+1):
            p += l[i]
            cumsum[i] = p

    print(*cumsum[:-1])

if __name__ == '__main__':
    main()

Solution (Python):
def right(a,n):
    sw = [0]*(n+1)
    for x,y in enumerate(a):
        x_min = max(0,x-y)
        x_max = min(n,x+y+1)
        sw[x_min] += 1
        sw[x_max] -= 1
    s = 0
    for i in range(n):
        s += sw[i]
        a[i] = s
    return a

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(min(k,50)):
    a = right(a,n)
a = [str(n) for n in a]
print(" ".join(a))

Solution (Python):
from itertools import accumulate

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

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

print(*A, sep=" ")

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys
import collections
 
mod = 10**9+7
sys.setrecursionlimit(mod) 
 
d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
 
N, K = LI()
A = LI()
 
if K > 50:
    print(" ".join([str(N) for i in range(N)]))
    sys.exit()
 
for i in range(K):
    A_new = [0 for i in range(N)]
    imos_table = [0 for i in range(N)]
 
    for j in range(N): 
        left = max(0, j - A[j])
        right = j + A[j] + 1
        imos_table[left] += 1
        if right >= N:
            pass
        else:
            imos_table[right] -= 1
    
    
    tmp = 0
    for j in range(N):
        tmp += imos_table[j]
        A_new[j] += tmp
 
    A = copy.deepcopy(A_new)
 
print(" ".join(map(str, A)))

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

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

from itertools import accumulate

aa

for _ in range(k):
    d = [0] * n

    for i, a in enumerate(aa):
        d[max(i-a, 0)] += 1
        end = i+1+a
        if end < n:
            d[end] -= 1

    d = list(accumulate(d))
    if aa == d:
        break
    aa = d


print(' '.join(str(a) for a in aa))

Solution (Python):
from itertools import accumulate

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

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

    print(*A, sep=" ")



if __name__ == "__main__":
    main()

Solution (Python):
from itertools import accumulate
n, k, *A = map(int, open(0).read().split())
for _ in range(min(k, 50)):
    B = [0] * (n+1)
    for i in range(n):
        B[max(0, i-A[i])] += 1
        B[min(n, i+A[i]+1)] -= 1
    *A, = accumulate(B)
print(*A[:n])

Solution (Python):

n, k = map(int, input().split())
a = list(map(int, input().split()))
for j in range(k):
  b = [0] * (n + 1)
  for i in range(n):
    left_edge = max(0, i-a[i])
    right_edge = min(i + a[i] + 1, n)
    b[left_edge] += 1
    b[right_edge] -= 1
  for i in range(1, n+1):
    b[i] = b[i] + b[i-1]
  b.pop(n)
  if a == b:
    break
  a = b.copy()
print(' '.join(str(b[i]) for i in range(n)))

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

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

A_list = np.array([0]+list(map(int, input().split())))

@njit
def update(A_list):

  for j in range(min(K,46)):
    new_A=np.zeros(N+2,dtype=np.int64)
    for i in range(1,N+1):
      
      mi=i-A_list[i]
      ma=i+A_list[i]
      if mi<0:
        mi=0
      if ma>N:
        ma=N
      
      new_A[mi]+=1
      new_A[ma+1]-=1

    A_list=np.cumsum(new_A)
    
    
    
      
  return(A_list)

A_list=update(A_list)
for i in range(1,N+1):
  print(A_list[i],end=" ")

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    for k in range(K):
        A_temp=[0]*(N+1)
        for i in range(N):
            A_temp[max(0,i-A[i])]+=1
            if i+A[i]+1<=N-1:
                A_temp[i+A[i]+1]-=1
            
        A[0]=A_temp[0]
        for j in range(1,N):
            A_temp[j]+=A_temp[j-1]
            A[j]=A_temp[j]
        for ai in A:
            if ai != N:
                break
        else:
            break
                
    print(' '.join([str(a) for a in A]))
    
if __name__ == "__main__":
    main()

Solution (Python):
import math

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

for i in range(min(41, K)):
  B = [0] * N
  for n, A_n in enumerate(A):
    B_min = max(0, n-A_n)
    b_max = min(N-1, n+A_n)
    B[B_min] += 1
    if b_max+1 < N:
      B[b_max+1] -= 1
  
  sum = 0
  for n in range(len(A)):
    sum += B[n]
    A[n] = sum

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

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

def culc(L):
    subL=[0]*(n+1)

    for i in range(n):
        temp=L[i]
        bottom=max(i-temp,0)
        top=min(i+temp,n-1)

        subL[bottom]+=1
        subL[top+1]-=1
    
    resL=[0]*n
    resL[0]=subL[0]
    for i in range(1,n):
        resL[i]=resL[i-1]+subL[i]

    return resL

for i in range(min(k,41)):
    A=culc(A)

print(*A)

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

dp = [0] * (N + 1)
for k in range(K):
    sta = [max(i-A[i], 0) for i in range(N)]
    end = [min(i+A[i]+1, N) for i in range(N)]
    for s in sta:
        dp[s] += 1
    for e in end:
        dp[e] -= 1
    for i in range(1, len(dp)-1):
        dp[i] += dp[i-1]
    B = dp[:-1]
    if A == B:
        break
    A = B
    dp = [0] * (N + 1)
 
print(' '.join(map(str, A)))

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

def culc(L):
    subL=[0]*(n+1)

    for i in range(n):
        temp=L[i]
        bottom=max(i-temp,0)
        top=min(i+temp,n-1)

        subL[bottom]+=1
        subL[top+1]-=1
    
    resL=[0]*n
    resL[0]=subL[0]
    for i in range(1,n):
        resL[i]=resL[i-1]+subL[i]

    return resL

for i in range(min(k,50)):
    A=culc(A)

print(*A)

Solution (Python):
n,k = map(int,input().split())
A = list(map(int,input().split()))
imos = [0]*(n+1)
for j in range(k):
    if j==0:
        arr = A
    else:
        arr = imos
    imos = [0]*(n+1)
    for i,a in enumerate(arr):
        imos[max(i-a, 0)] += 1
        imos[min(i+a+1, n)] -= 1
    for k in range(1, len(imos)):
        imos[k] = imos[k]+imos[k-1]
    imos = imos[:-1]
    if set(imos)=={n}:
        break
print(*imos)

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
def main(N, K, A):
  for _ in range(min(K, 42)):
    A_ = np.zeros_like(A)
    for n in range(N):
      A_[max(0, n - A[n])] += 1
      if n + A[n] + 1  < N:
        A_[n + A[n] + 1] -= 1
    A = A_.cumsum()
        
  return A

print(*main(N, K, A))

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

@jit('i4[:](i4,i4,i4[:])',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 jit

@jit('i2[:](i2,i2,i2[:])',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 jit

@jit('i2[:](i2,i2,i2[:])')
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

import math

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

@njit
def solve(n,k,a):
    for i in range(k):
        new = np.zeros_like(a)
        for j in range(n):
            distance = j - a[j]
            if distance < 0:
                distance = 0
            last =  j + a[j]
            if last > n-1:
                last = n-1
            new[distance]+=1
            if last+1 < n:
                new[last+1]-=1
        a = np.cumsum(new)
        if np.all(a==n):
            break
    return a

a = solve(n,k,a)
print(" ".join(a.astype(str)))