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 = list(map(int, input().split()))
A = list(map(int, input().split()))
for _ in range(min(K, 42)):
    B = [0]*N
    for i in range(N):
        left = max(0, i-A[i])
        right = min(N-1, i+A[i])
        B[left] += 1
        if right+1 <= N-1:
            B[right+1] -= 1
    for i in range(N-1):
        B[i+1] += B[i]
    A = B[:]
print(*A)

Solution (Python):
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    
    if K > 41:
        K = 41
    
    for k in range(K):
        B = [0 for i in range(N)]
        for i in range(N):
            low = max(0,i-A[i])
            high = min(N-1,i+A[i])
            B[low] += 1
            if high+1 < N:
                B[high+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
    
    print(*A)
    
if __name__ == '__main__':
    main()

Solution (Python):

import sys


def solve(N: int, K: int, A: "List[int]"):

    for k in range(K):
        B = [0] * N

        for i in range(N):
            l = max(0, i - A[i])
            r = 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.copy()
        if sum(A) == N*N:
            break
    print(*A)

    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):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

INF = float("inf")


N,K = map(int,input().split())
A = list(map(int,input().split()))
if N == 1:
    print(1)
else:
    
    old = A
    for _ in range(K):
        li = [0]*N
        for i in range(N):
            MIN = max(0,i-old[i])
            MAX = min(N-1,i+old[i])
            li[MIN] += 1
            if MAX != N-1:
                li[MAX+1] -= 1
        s = 0
        for i in range(N):
            s += li[i]
            old[i] = s
        if min(old) == N:
            break
    print(*old)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations, accumulate
from bisect import bisect_left, bisect_right  

N, K = read_ints()
A = read_ints()







for _ in range(min(50, K)):
    imos = [0] * (N + 1)
    for i, d in enu(A):
        imos[max(i - d, 0)] += 1
        imos[min(i + d + 1, N)] -= 1
    A = list(accumulate(imos))[:-1]
print(*A)

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

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

from itertools import accumulate

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

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

  A = list(accumulate(B))
  if A.count(N)==N: break
  
  

print(*A)

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

diff_list = [0 for num in range(n)]
diff_list[0] = a_in[0]
for i in range(1, n):
    diff_list[i] = a_in[i] - a_in[i-1]

itr = k
if k > 41:
    itr = 41
for i in range(itr):
    new_list = [0 for num in range(n)]
    d_sum = 0
    for j, d in enumerate(diff_list):
        d_sum += d
        if j-d_sum > 0:
            new_list[j-d_sum] += 1
        else:
            new_list[0] += 1
        if d_sum+j+1 < n:
            new_list[j+d_sum+1] -= 1
    
    diff_list = new_list.copy()

ans = 0
for d in diff_list:
    ans += d
    print(ans, end= ' ')

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))+[0]
s = [0 for _i in range(n+1)]
for i in range(n):
    s[max(0, i-a[i])] += 1
    s[min(n, i+a[i]+1)] -= 1   
a = s.copy()+[0]
for j in range(min(100, k-1)):
    t = [0 for _i in range(n+1)]
    for i in range(n):
        a[i] += a[i-1]
        t[max(0, i-a[i])] += 1
        t[min(n, i+a[i]+1)] -= 1
    a = t.copy()+[0]
for i in range(1, n):
    a[i] += a[i-1]
print(*a[:n])

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):
        l = max(0, i - a[i])
        r = min(n-1, i + a[i])
        b[l] += 1
        if r + 1 < n:
            b[r + 1] -= 1
    ee = True
    a[0] = b[0]
    if a[0] < n:
        ee = False
    for i in range(1, n):
        a[i] = a[i-1] + b[i]
        if a[i] < n:
            ee = False
    if ee == True:
        break

print(*a)

Solution (Python):
def resolve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for _ in range(min(k,100)):
        dp = [0] * (n + 1)
        for index, i in enumerate(a):
            dp[max(0, index - i)] += 1
            dp[min(n, index + i + 1)] -= 1
        a[0] = dp[0]
        for i in range(1, n):
            a[i] = a[i - 1] + dp[i]
    print(*a)


if __name__ == '__main__':
    resolve()

Solution (Python):
def resolve():
        n, k = map(int, input().split())
        a = list(map(int, input().split()))
        bn1 = [0] * n
        s = 0
        t = 0
        chec = 0
        for _ in range(k):
            for i in range(n):
                b1 = max(i - a[i], 0)
                b2 = min(i + a[i], n - 1)
                bn1[b1] += 1
                if b2<n-1:
                    bn1[b2+1] -= 1
            for i in range(n):
                s += bn1[i]
                a[i] = s
                if s==n:
                    chec+=1
            s = 0
            if chec == n:
                break
            chec = 0
            bn1 = [0] * n
        c = [str(x) for x in a]
        L = " ".join(c)
        print(L)
resolve()

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

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

maxK = min(50,K)
t = 1
while t<=maxK:
    nextA = [0]*N
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1,i+A[i])
        nextA[l] += 1
        if r+1<=N-1:
            nextA[r+1] += -1
    for i in range(1,N):
        nextA[i] = nextA[i-1] + nextA[i]
    A = nextA[:]
    t+=1
print(*nextA)

Solution (Python):
import itertools

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

for _ in range(K):
    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
    B = list(itertools.accumulate(B))
    A = B.copy()
    if A == [N] * N:
        break
print(*A)

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
s_readline = sys.stdin.readline


def main():

    N, K = map(int, readline().split())
    A = np.array(list(map(int, readline().split())), np.int32)

    K = min(N, K)
    ans = solve(N, K, A).tolist()
    print(' '.join(map(str, ans)))


@njit('i4[:](i4,i4,i4[:])', cache=True)
def solve(N, K, A):

    for k in range(K):

        B = np.zeros(N, np.int32)
        for i in range(N):
            l = max(0, i - A[i])
            r = i + A[i] + 1
            B[l] += 1
            if r <= N - 1:
                B[r] -= 1

        s = B[0]
        for i in range(N - 1):
            B[i + 1] = B[i + 1] + B[i]
            s += B[i + 1]

        A = B

        if s == N * N:
            break

    return A


if __name__ == '__main__':
    main()

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

"""
明るさが一定値を超えると計算しなくて良い
一定？d > math.floort(N/2)
"""
if K > 50:
    b = [str(N)] * N
    print(" ".join(b))
    sys.exit()

lamps = [[0 for i in range(N)] for j in range(K + 1)]
lamps[0] = A

"""
累積和〜
"""
for i in range(K):
    if lamps[i] == [N for i in range(N)]:
        ans = [str(N) for i in range(N)]
        print(" ".join(ans))
    tmps = [0 for i in range(N)]
    for j in range(N):
        w = lamps[i][j]
        tmps[max(0, j - w)] += 1
        r = min(N-1, j + w)
        if r + 1 < N:
            tmps[r + 1] -= 1
    hoge = 0
    for j in range(N):
        hoge += tmps[j]
        lamps[i + 1][j] = hoge
ans = lamps[-1]
ans = map(str, ans)
print(" ".join(ans))

Solution (Python):
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):
        B[max(0, j-A[j])] += 1
        B[min(n, j+A[j]+1)] -= 1
    A[0] = B[0]
    for j in range(1, n):
        A[j] = A[j-1]+B[j]
    if A == [n]*n:
        print(*A)
        exit()
print(*A)

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

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):
        l = max(0,j-A[j])
        r = j+A[j]+1
        B[l] += 1
        if r < N:
            B[r] -= 1
    for j in range(1, N):
        B[j] += B[j-1]

    A = B

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

print(*A)

Solution (Python):
from itertools import accumulate

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

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

for j in range(k):
    if j > 41:
        break

    b = [0] * n

    for i in range(n):
        b[max(0, i - a[i])] += 1
        
        if i + a[i] + 1 < n:
            b[i + a[i] + 1] -= 1

    a = list(accumulate(b))

print(*a)

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

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

@njit(cache=True)
def calc(a, step):
    b = np.array([0]*N)
    for i in range(N):
        left = int(max(0, i-a[i]))
        right = int(min(N-1, i+a[i]))
        b[left] += 1
        if right + 1 < N:
            b[right+1] -= 1
    b = np.cumsum(b)
    
    if np.all(a==b) or step>=K:
        return b
    else:
        step += 1
        return calc(b, step)

ans = calc(A, 1)
ans = [str(x) for x in ans]
print(" ".join(ans))

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N,K = IL()
A = IL()
if K > 39:
  A = [N for i in range(N)]
  print(*A)
  exit()
  
while True:
  if K == 0:
    break
  imosu = [0 for i in range(N+2)]
  for i in range(N):
    l = max(0,i-A[i])
    r = min(N-1,i+A[i])
    imosu[l] += 1
    imosu[r+1] -= 1
  A = [0]
  for i in range(N):
    A.append(A[-1]+imosu[i])
  A = A[1:]
  K -= 1
  if min(A) == N:
    break
  
print(*A)

Solution (Python):
n,k=map(int,input().split())
l=list(map(int,input().split()))
from itertools import accumulate
def update(a):
    ret=[0]*len(a)
    for i,x in enumerate(a):
        ret[max(i-x,0)]+=1
        r=min(n-1,i+x)
        if r==n-1:continue
        ret[r+1]-=1
    return list(accumulate(ret))
for i in range(min(50,k)):
    l=update(l)
print(*l)

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

    for k in range(K):
        imos = [0] * (N+1)
        for i in range(N):
            imos[min(N,i+A[i]+1)] -= 1
            imos[max(0,i-A[i])] += 1
        
        A[0] = imos[0]
        all_N = True
        for i in range(1,N):
            A[i] = A[i-1] + imos[i]
            if A[i] != N:
                all_N = False
        
        if all_N:
            break

    print(*A)

if __name__ == '__main__':
    solve()

Solution (Python):
from sys import stdin, setrecursionlimit
from itertools import accumulate


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(k):
        tmp = [0] * (n + 1)
        for j in range(n):
            tmp[max(0, j - a[j])] += 1
            tmp[min(n, j + a[j] + 1)] -= 1
        a = list(accumulate(tmp))[:n]
        for ai in a:
            if ai != n:
                break
        else:
            break
    print(*a)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = read_input()
K = min(K, 41)

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

        B[start] += 1
        if end+1 < N:
            B[end+1] -= 1
    for i in range(1, N):
        B[i] += B[i-1]
    A = B.copy()


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

Solution (Python):
n,k,*a=map(int,open(0).read().split())
for _ in range(k):
  b=[0]*n
  for i,q in enumerate(a):
    b[max(0,i-q)]+=1
    if i+q+1<n:
      b[i+q+1]-=1
  for i in range(1,n):
    b[i]+=b[i-1]
  if a==b:
    break
  a=b[:]
print(*a)

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

K = min(K, 41)
dp = [[0]*N for _ in range(K)]

for i in range(N):
    temp = S[i]
    m = max(0, i-temp)
    dp[0][m] += 1
    if N > i+temp+1:
        dp[0][i+temp+1] -= 1

for i in range(K-1):
    temp = 0
    for j in range(N):
        temp += dp[i][j]
        m = max(0, j-temp)
        dp[i+1][m] += 1
        if N > j+temp+1:
            dp[i+1][j+temp+1] -= 1

ans = [0]*N
ans[0] = dp[K-1][0]

for i in range(1, N):
    ans[i] = ans[i-1] + dp[K-1][i]

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

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

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

for _ in range(K):
    B = [0 for _ in range(N)]
    end = True

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

        B[left] += 1
        if right + 1 < N:
            B[right + 1] -= 1

    for i in range(N):
        if i > 0:
            B[i] += B[i - 1]
        if B[i] != N:
            end = False

    A = B

    if end:
        break

for a in A:
    print(a, end=" ")

print()

Solution (Python):
import copy

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

for k in range(min(K, 41)):
    B = [0 for _ in range(N)]
    for i in range(N):
        left = max(i-A[i], 0)
        right = min(i+A[i], N-1)
        B[left] += 1
        if (right+1<N):
            B[right+1] -= 1
    for i in range(1, N):
        B[i] += B[i-1]
    A = copy.deepcopy(B)
print(" ".join(list(map(str, A))))

Solution (Python):
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

n,k = iim()
A = iil()
'''
A = [0]*200000
上記でtryしても41回で全て明るさ200000になる
'''

def imos(l):
    n = len(l)
    tmp = [0]*n
    for i,item in enumerate(l):
        l = max(0,i-item)
        r = min(n-1,i+item)
        tmp[l] += 1
        if r+1 < n:
            tmp[r+1] -= 1
    for i in range(1,n):
        tmp[i] += tmp[i-1]
    return tmp

for _ in range(min(k,100)):
    A = imos(A)


print(*A)

Solution (Python):
def resolve():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(k):
        nxt = [0]*n
        for j in range(len(a)):
            r = min(j + a[j], n-1) 
            l = max(j-a[j], 0) 
            nxt[l] += 1
            if r+1 < n:
                nxt[r+1] -= 1
        b = [0] *n
        for j in range(len(a)):
            if j== 0:
                b[j] = nxt[j]
            else:
                b[j] = (nxt[j]+b[j-1])
        a, b = b, a
        if a == b:
            break
    print(*a)
resolve()

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



input = sys.stdin.buffer.readline


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

A = np.array(input().split(), dtype=np.int64)





@njit(cache=True)
def loop(A):
    for i in range(K):
        
        cnt = np.zeros_like(A)
        for j, x in enumerate(A):
            
            l = max(j-x,0)
            r = min(j+x+1,N)
            cnt[l] += 1
            if r<N:
                cnt[r] -= 1
            
            
        
        
        
        A = np.cumsum(cnt)
        if A[0] == A[N-1] == N:
            break
        
    return A

A = loop(A)
print(*A)

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


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

        A = np.cumsum(B)[:-1]

        if np.all(A == N):
            return A

    else:
        return A


A = solve(N, K, A)
for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])

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

Solution (Python):
N,K=map(int,input().split())
ls=list(map(int,input().split()))
for _ in range(K):
  if ls==[N]*N:
    break
  else:   
    R=[0]*(N)
    for i in range(N):
      R[max([0,i-ls[i]])]+=1
      if i+ls[i]+1<N:
        R[i+ls[i]+1]-=1  
    ls[0]=R[0]
    for i in range(N-1):
      ls[i+1]=ls[i]+R[i+1]   
for i in range(N):
  print(ls[i],end=" ")

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

import math
K = min(K, 43)
for k in range(K):
  light = [0] * (N+1)
  for i in range(N):
    start = max(0,i-A[i])
    end = min(N-1, i+A[i])
    light[start] += 1
    light[end+1] -= 1
  for i in range(1,N):
    light[i] += light[i-1]
    
  A = light

light.pop()
print(" ".join(map(str,light)))

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

for i in range(k):
    s = [0] * (n + 1)
    for j in range(n):
        l = max(0, j - a[j])
        r = min(n, j + a[j]+1)
        s[l] += 1
        s[r] += -1
    m = s[0]
    for j in range(1,n+1):
        s[j] += s[j-1]
        if j < n:
            m = min(m, s[j])
    a = s[:-1]
    if m == n:
        print(' '.join(map(str, a)))
        exit()
print(' '.join(map(str, a)))

Solution (Python):
import sys
input=sys.stdin.readline
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    zeros=[0]*n

    if min(a)==n:
        print(*a)
        exit()

    for i in range(k):
        x=zeros.copy()
        for j in range(n):

        
            l=max(0,j-a[j])
            r=min(j+a[j]+1,n)
            
            x[l]+=1
            if r!=n:
                
                x[r]+=-1
            
        ruiseki=[0]*n
        ruiseki[0]=x[0]
        a[0]=ruiseki[0]
        for i in range(1,n):
            ruiseki[i]=ruiseki[i-1]+x[i]
            a[i]=ruiseki[i]
        if min(a)==n:
            print(*a)
            exit()
 
        
    print(*a)
if __name__=="__main__":
    main()

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from copy import copy
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    cur = copy(a)

    for cnt in range(k):
        cum = [0] * (n + 1)
        for i, x in enumerate(cur):
            left = max(0, i - x)
            cum[left] += 1
            right = min(i + x + 1, n)
            cum[right] -= 1

        cur[0] = cum[0]
        for i in range(n-1):
            cur[i + 1] = cur[i] + cum[i + 1]

        if all([j == n for j in cur]):
            break

    print(*cur[:n])

if __name__ == '__main__':
    main()

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = lr() + [0]

for _ in range(min(K, 41)):
    next = [0] * (N+1)
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    for i in range(N):
        next[i+1] += next[i]
    A = next.copy()

print(*A[:-1])

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time
from decimal import *


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False


def pl(x, d):
        return x - d - 0.5


def pr(x, d):
    return x + d + 0.5


def b(A, K):
    for k in range(K):
        ans = []
        for i in range(len(A)):
            c = 0
            for j in range(len(A)):
                l = pl(j, A[j])
                r = pr(j, A[j])

                if i >= l and i <= r:
                    c += 1
            ans.append(c)
        A = ans
        if ans[-1] == len(A):
            print(k, ans)
            return ans
    return A

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

    for i in range(min(100, K)):
        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)
    
    
    
    

    

    
    
    
    
    
    
    
    

    
    
    
    

    

    
    
    
    
    
    
    
    
    
    
    

    
    
    
    

        
        
        
    
    
    


if __name__ == '__main__':
    main()

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

for n_iter in range(k):
    b = [0] * n
    for i in range(n):
        left = max(0, i - a[i])
        right = min(n-1, i + a[i])
        b[left] += 1
        if right + 1 < n: 
            b[right + 1] -= 1

    a[0] = b[0]
    for i in range(1, n):
        b[i] += b[i-1]
        a[i] = b[i]
    
    if n_iter >= 50:
        break

print(*a)

Solution (Python):
def Csum(a):
    b,c=[0],0
    for i in range(len(a)):
        c+=a[i]
        b.append(c)
    return b

n,k=map(int,input().split())
a=list(map(int,input().split()))
if k>100:
    a=[n]*n
    print(*a)
    exit()
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
    a=Csum(b)[1:-1]
print(*a)

Solution (Python):
import math

N, K = map(int, input().split())
K = min(41, K)
A = list(map(int, input().split()))
A.insert(0, 0)

def operation():
  global A, N
  B = [0] * (N+1)
  for i in range(1, N+1):
    left = max(1, math.ceil(i - A[i] - 0.5))
    right = min(N, math.floor(i + A[i] + 0.5))
    B[left] += 1
    if right+1 <= N:
      B[right+1] -= 1
  for i in range(1, N+1):
    B[i] += B[i-1]
  return B


operation()




for _ in range(K):
  A = operation()

print(*A[1:])

Solution (Python):
def main():
    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(i - A[i], 0)] += 1
            B[min(i + A[i] + 1, N)] -= 1
        for i in range(1, N):
            B[i] += B[i-1]
        A = B
        if sum(A[:-1]) == N * N:
            break
    print(' '.join(str(i) for i in A[:-1]))
main()

Solution (Python):

import copy

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

for i in range(K):
    B = [0 for k in range(N)]
    for j in range(N):
        L = A[j]
        l = max(j-L, 0)
        r = min(j+L, N-1)
        B[l] += 1
        if r + 1 < N:
            B[r+1] -= 1
    for j in range(1, N):
        B[j] += B[j-1]
    A = copy.deepcopy(list(B))
    if len(set(A)) == 1 and A[0] == N:
        break
print(*A)

Solution (Python):
import sys
import copy
from itertools import accumulate
input=sys.stdin.readline
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    ans = copy.deepcopy(A)
    for _ in range(K):
        cumsum = [0]*N
        for i,a in enumerate(ans):
            l = max(0,i-a)
            r = min(N-1,i+a)
            cumsum[l] += 1
            if r+1 < N:
                cumsum[r+1] -= 1
        ans = list(accumulate(cumsum))
        if ans[0] == N:
            break
    print(*ans)
    
if __name__ == '__main__':
    main()