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

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



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

for r 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
    cb = [0]*N
    flag = True
    for i in range(N):
        cb[i] = min(cb[i-1]+b[i],N)
        if cb[i] != N:
            flag = False
    A = cb[:]
    if flag:
        break

print(*A)

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


for _ in range( min( k, 41 ) ): 
    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( " ".join( list( map( str, a ) ) ) )

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

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

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

def sim(a):
    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]
    return b

for i in range(min(k,41)):
    a = copy.copy(sim(a))
print(*a)

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

for j in range(min(k,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.copy()
print(*B)

Solution (Python):
import itertools
def main():
    n,k = tuple([int(t)for t in input().split()])

    a = tuple([int(t)for t in input().split()])

    for _ in range(min(41,k)):
        b = [0]*(n+1)
        for i in range(n):
            l = max(0,i-a[i])
            r = min(n,i+a[i]+1)
            b[l] += 1
            b[r] -= 1
        a = list(itertools.accumulate(b))[:n]

    print(*a)



if __name__ == "__main__":
    main()

Solution (Python):
from itertools import accumulate
n,k,*a=map(int,open(0).read().split())
for _ in range(k):
    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))
    if a==[n]*n:break
print(" ".join(map(str,a)))

Solution (Python):
from math import log2

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    if K > log2(N)+ 50:
        return print(*[N]*N,sep = " ")
    for _ in range(K):
        imos = [0]*(N + 1)
        for i in range(N):
            imos[max(0,i  - A[i])] += 1
            imos[min(N,i + 1 + A[i])] -= 1
        for j in range(N):
            imos[j+1] += imos[j]
        A = imos[:N].copy()
    print(*A,sep=" ")
    return

if __name__ == "__main__":
    main()

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
dp = [(0, 0)] * n
changed = set(range(n))
for j in range(k):
    for i in changed:
        l = max(0, i - a[i])
        r = min(n - 1, i + a[i])
        dp[i] = (l, r)
    imos = [0] * n
    for i in range(n):
        l, r = dp[i]
        imos[l] += 1
        if r < n - 1:
            imos[r + 1] -= 1
    tmp = 0
    for i in range(n):
        tmp += imos[i]
        a[i] = tmp
    if imos[0]==n:
        break
print(*a)

Solution (Python):
from itertools import accumulate

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

def do(A):
  B = [0] * (N+2)
  for i, a in enumerate(A, 1):
    l = max(i - a, 0)
    r = min(i + a + 1, N+1)
    B[l] += 1
    B[r] -= 1
  B = list(accumulate(B))
  return B[1:-1]

def check(A):
  for a in A:
    if a < N:
      return False
  return True

for i in range(K):
  A = do(A)
  if check(A):
    print(*A)
    quit()

print(*A)

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

for i in range(1,K+1):
  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
    
  if B[0]==N:
    x = 1
  else:
    x = 0
  for i in range(1,N):
    B[i] += B[i-1]
    if B[i]==N:
      x += 1
  A = B.copy()
  if (x==N)or(i==K):
    break
    
print(' '.join(list(map(str,A))))

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

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

    S = [0]*N
    S[0] = t[0]
    for i in range(1, N):
        S[i] = S[i-1] + t[i]

    A = S.copy()
    if all(a == N for a in A):
        print(*A)
        exit()
print(*S)

Solution (Python):

import sys

N,K,*A = map(int, sys.stdin.buffer.read().split())

for _ in range(K):
  Anext = [0 for _ in range(N+1)]
  for i in range(N):
    Anext[max(0,i-A[i])] += 1
    Anext[min(N,i+A[i]+1)] -= 1
  cumsum = 0
  for i in range(N):
    cumsum += Anext[i]
    A[i] = cumsum
  if min(A)==N:
    break

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

Solution (Python):
n,k,*a=map(int,open(0).read().split())

for _ in range(k):
    tab=[0]*n
    for i in range(n):
        q=a[i]
        l=max(0,i-q)
        tab[l]+=1
        r=i+q+1
        if r<n:
            tab[r]-=1
    b=[tab[0]]
    for i in range(n-1):
        b.append(b[-1]+tab[i+1])
        
    if a==b:
        break
    else:
        a=b[:]
print(*a)

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

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

new_a = [0 for i in range(n)]
for i in range(k):
    for j in range(n):
        new_a[max(j-a[j], 0)] += 1
        if j+a[j]+1 < n:
            new_a[j+a[j]+1] += -1
    for j in range(n):
        if j > 0:
            new_a[j] += new_a[j-1]
    if new_a == [n for i in range(n)]:
        a = copy.copy(new_a)
        break
    a = copy.copy(new_a)
    new_a = [0 for i in range(n)]

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

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

for i in range(min(k,500)):
    ans=[0]*(n)
    for j in range(n):
        l=max(0,j-a[j])
        r=j+1+a[j]
        ans[l]+=1
        if r<n:
            ans[r]-=1
    for z in range(n-1):
        ans[z+1]+=ans[z]
    a=ans
print(" ".join(list(map(str,ans))))

Solution (Python):

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

if K > 41:
    K = 41

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

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

    for i in range(1, N):
        D[i] += D[i-1]
    A = D


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

Solution (Python):
import sys


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

    for i in range(K):
        imos = [0] * (N + 1)
        for j in range(N):
            
            l, r = max(0, j - A[j]), min(j + A[j], N - 1)
            
            imos[l] += 1
            imos[r + 1] -= 1
        for k in range(N):
            imos[k + 1] = imos[k] + imos[k + 1]
        A = imos[:N]
        if A.count(N) == N:
            print(*A)
            sys.exit()

    print(*imos[:N])


if __name__ == "__main__":
    main()

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

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

    S = [0]*N
    S[0] = t[0]
    for i in range(1, N):
        S[i] = S[i-1] + t[i]

    A = S.copy()
print(*S)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)

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

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

K = min(K, 100)

for _ in range(K):
    imos = [0] * (N + 1)

    for i in range(N):
        a = A[i]
        s = max(0, i - a)
        e = min(N, i + a + 1)
        imos[s] += 1
        imos[e] -= 1

    nxt = [0] * N
    t = 0
    for i in range(N):
        t += imos[i]
        nxt[i] = t

    A = nxt

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

Solution (Python):
import copy
N, K = map(int, input().split())
A = list(map(int, input().split()))
lights = [0] * N

for _ in range(min(K, 42)):
    lights = [0] * N
    for i, flash in enumerate(A):
        lights[max(0, i-flash)] += 1
        if i+flash < N-1:
            lights[i+flash+1] -= 1
    for i in range(1, N):
        lights[i] += lights[i-1]
    A = copy.deepcopy(lights)

for i in A:
    print(int(i),end=' ')
print()

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

for i in range(K):
  l = [0]*N
  for i in range(N):
    m,p = i-A[i],i+A[i]
    if p+1 <= N-1:
      l[p+1] -= 1
    if m >= 0:
      l[m] += 1
    if m < 0:
      l[0] += 1
  for i in range(N-1):
    l[i+1] += l[i]
  A = copy.deepcopy(l)
  if A[0] == N:
    break 
print(*A)

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

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N,K = LI()
    a = LI()

    for _ in range(K):
        x = [0] * N
        for i in range(N):
            s = i - a[i]
            if s < 0: s = 0
            x[s] += 1
            t = i + a[i] + 1
            if t < N:
                x[t] -= 1
        a = []
        cnt = 0
        finish = True
        for i in range(N):
            cnt += x[i]
            if cnt < N: finish = False
            a.append(cnt)
        if finish: break
    print(*a,sep=' ')


if __name__ == '__main__':
    main()

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

    dp = [[0]*n for _ in range(k+1)]
    for i in range(n):
        dp[0][i] = A[i]

    flag = False
    for i in range(1,k+1):
        pos = [0]*n
        neg = [0]*n

        for j in range(n):
            pwr = dp[i-1][j]
            pos[max(0,j-pwr)]+=1
            neg[min(n-1,j+pwr)]+=1

        ac_pos = 0
        ac_neg = 0
        for j in range(n):
            ac_pos += pos[j]
            ac_neg += neg[j]
            pos[j] = ac_pos
            neg[j] = ac_neg

        if pos[0]==n and neg[n-2]==0:
            flag = True
            break

        dp[i][0] = pos[0]
        for j in range(1,n):
            dp[i][j] = pos[j] - neg[j-1]

    
    if flag:
        for j in range(n-1):
            print(n, end=" ")  
        print(n)

    else:
        for j in range(n-1):
            print(dp[i][j], end=" ")
        print(dp[i][n-1])
main()

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

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

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

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

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

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

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

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
dp = [(0, 0)] * n
changed=set(range(n))
for j in range(k):
    for i in changed:
        l = max(0, i - a[i])
        r = min(n - 1, i + a[i])
        dp[i] = (l, r)
    imos = [0] * n
    for i in range(n):
        l, r = dp[i]
        imos[l] += 1
        if r < n - 1:
            imos[r + 1] -= 1
    tmp = 0
    for i in range(n):
        tmp += imos[i]
        a[i] = tmp
    if j>50:
        break
print(*a)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(k):
  l = [0 for i in range(n)]
  r = [0 for i in range(n)]
  for i in range(n):
    l[max(0, i-a[i])] += 1
    r[min(i+a[i], n-1)] += 1
    
  lighted = 0
  for i in range(n):
    lighted += l[i]
    a[i] = lighted
    lighted -= r[i]
  if len(set(a)) == 1 and a[0] == n:
    break
print(' '.join(list(map(str, a))))

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

Solution (Python):
import sys
import numpy as np
from numba import njit
 
readline = sys.stdin.readline
 
@njit('i8,i8,i8[::1]',cache=True)
def loop(n,k,a):
    for j in range(k):
        b = np.zeros(n+1, dtype=np.int64)
        for i in range(n):
            b[max(i-a[i], 0)] += 1
            b[min(i+a[i]+1, n)] -= 1
        a = np.cumsum(b)[:-1]
        if np.all(a==n):
            return(a)
            break
    else:
        return(a)
 
 
n, k = map(int, readline().split())
a = np.array(readline().split(), dtype=np.int64)
 
ans = loop(n,k,a)
print(*ans)

Solution (Python):

import sys


def solve(N: int, K: int, A: "List[int]"):
    for idx in range(min(50,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
        
        add = 0
        for i in range(N):
            add += B[i]
            A[i] = add
    
    print(*A)


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):
"""
https://atcoder.jp/contests/tokiomarine2020/submissions/14229099
"""
N,K = map(int,input().split())
A = list(map(int,input().split()))

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(min(K,75)):
    A = update(A)

print(*A)

Solution (Python):
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
d = [0]*(n+1)
for x in range(k):
    for i in range(n):
        l = max(0,i-a[i])
        r = min(n-1,i+a[i])+1
        d[l] += 1
        d[r] -= 1
    for i in range(n): d[i+1] += d[i]
    if x == k-1: break
    for i in range(n):
        if d[i] != n: break
    else:
        break
    a = d[:]
    d = [0]*(n+1)
print(*d[:n])

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline



def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    n, k = geta(int)
    a = tuple(geta(int))

    def update(b):
        r = [0] * n
        for i, bi in enumerate(b):
            i1 = max(0, i - bi)
            i2 = min(n - 1, i + bi)
            r[i1] += 1

            if i2 < n - 1:
                r[i2 + 1] -= 1

        updated = (not r[0] == b[0])
        for i in range(1, n):
            r[i] += r[i - 1]
            if r[i] != b[i]:
                updated = True

        return r, updated

    for i in range(k):
        a, updated = update(a)
        if not updated:
            break

    print(*a, sep=" ")


if __name__ == "__main__":
    main()

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

lenA = len(A)
for i in range(K):
    B = [0 for _ in range(lenA)]

    for j in range(lenA):
        num = A[j]

        if j - num >= 0:
            B[max(0, j - num)] += 1
        else:
            B[0] += 1
        if j + num + 1 < lenA:
            B[min(lenA, j + num + 1)] -= 1

    for i in range(1, lenA):
        B[i] = B[i-1] + B[i]
    if all([a == b for a, b in zip(A,B)]):

        break
    else:
        A = B

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

Solution (Python):
import math
from sys import stdin,stdout

from heapq import heapify,heappop,heappush
import collections

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


for i in range(min(k,42)):
    
    pr=[0]*n
    for x,d in enumerate(a):
        if d==0:
            pr[x]+=1
            if x!=n-1:
                pr[x+1]-=1
            continue
        l=math.floor(x-d)
        r=math.floor(x+d)
        l=max(0,l)
        r=min(n-1,r)
        pr[l]+=1
        if r!=n-1:
            pr[r+1]-=1
    
    for m in range(1,n):
        pr[m]+=pr[m-1]
    
    a[:]=pr


        

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

Solution (Python):
N,K = map(int,(input().split()))
A = list(map(int,(input().split())))
for _ in range(min(K,100)):
    s = [0]*(N+1)
    for i in range(N):
        l = max(i - A[i],0)
        r = min(i + A[i] + 1,N)
        s[l] += 1
        s[r] -= 1
    for i in range(1,N):
        s[i] += s[i-1]
    for i in range(N):
        A[i] = s[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+1)
    for j in range(N):
        l=max(0,j-A[j])
        r=min(N-1,j+A[j])
        B[l]+=1
        B[r+1]-=1
    for j in range(1,N):
        B[j]=B[j]+B[j-1]
    ok=True
    for j in range(N):
        if B[j]!=N:
            ok=False
            break
    if ok:
        print(*B[:N])
        exit()
        
    A=B.copy()
print(*A[:N])

Solution (Python):
N, K = map(int, input().split())
*A, = map(int, input().split())
for _ in range(min(K, 50)):
    counter = [0] * (N+2)
    for i, a in enumerate(A, 1):
        counter[max(0, i - a)] += 1
        counter[min(N + 1, i + a + 1)] += -1
    for i in range(1, len(counter) - 1):
        counter[i] += counter[i-1]
    A = counter[1:N+1]
print(*A)

Solution (Python):



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

    for i in range(min(K,50)):
        dm = [0]*N
        for x in range(N):
            dm[max(x - A[x],0)]+=1
            if x+A[x]+1<N:
                dm[x+A[x]+1]+=-1
        for j in range(1,N):
            dm[j]=dm[j-1]+dm[j]
        A[:] = dm[:]
    print(*A)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate
from math import log2

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

for j in range(k):
    a01 = [0] * (n + 1)
    for i, ai in enumerate(a):
        l, r = max(0, i - ai), min(i + ai + 1, n)
        a01[l] += 1
        a01[r] -= 1
    a = list(accumulate(a01))
    if all(ai == n for ai in a[:-1]):
        break
print(*a[:-1])

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


def query(lamps):
    counts = [0] * n
    for idx, power in enumerate(lamps):
        start, end = idx - power, idx + power
        if start < 0:
            start = 0
        counts[start] += 1

        if end >= n-1:
            continue
        counts[end+1] -= 1

    now = 0
    for idx, count in enumerate(counts):
        now += count
        lamps[idx] = now


def full_check(counts, full):
    for count in counts:
        if count == full:
            continue
        else:
            return False

    return True


for _ in range(k):
    query(A)
    if full_check(A, n):
        break

print(*A)

Solution (Python):
import math
from sys import stdin,stdout

from heapq import heapify,heappop,heappush
import collections

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


for i in range(min(k,100)):
    
    pr=[0]*n
    for x,d in enumerate(a):
        if d==0:
            pr[x]+=1
            if x!=n-1:
                pr[x+1]-=1
            continue
        l=math.floor(x-d)
        r=math.floor(x+d)
        l=max(0,l)
        r=min(n-1,r)
        pr[l]+=1
        if r!=n-1:
            pr[r+1]-=1
    
    for m in range(1,n):
        pr[m]+=pr[m-1]
    
    a[:]=pr


        

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

Solution (Python):
N, K = map(int, input().split())
*A, = map(int, input().split())
for k in range(41):
    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
    for i in range(1, N): B[i] += B[i-1]
    A = B
    if k == K - 1: break
print(*A)

Solution (Python):
from copy import deepcopy

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

for _ in range(k):
    if sum(As) == n * n:
        break
    Bs = [0] * n
    for i in range(n):
        l = max(0, i - As[i])
        r = min(n - 1, i + As[i])
        Bs[l] += 1
        if r + 1 < n:
            Bs[r + 1] -= 1
    for i in range(1, n):
        Bs[i] += Bs[i - 1]
    As = Bs

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

Solution (Python):
from itertools import accumulate

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*(n+1)

if k > 41:
    k = 41

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
    a = list(accumulate(b))
    for i in range(n+1):
        if a[i] >= n:
            a[i] = n

print(*a[:-1])

Solution (Python):
from itertools import accumulate
import sys

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

for cnt in range(k):
    tmp = [0] * (n + 2)
    for i in range(n):
        power = arr[i]
        left = max(0, i - power + 1)
        right = min(n + 1, i + power + 2)
        tmp[left] += 1
        tmp[right] -= 1
    arr = list(accumulate(tmp))[1:-1]
    if cnt > 40:
        arr = [n] * n
        print(*arr)
        sys.exit()

print(*arr)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(min(K,300)):
    imos = [0]*(N+1)
    for i, ai in enumerate(A):
        imos[max(0, i-ai)] += 1
        imos[min(N, i+ai+1)] -= 1
    A = [imos[0]]
    for i in range(1, N):
        A += [imos[i]+A[i-1]]
print(' '.join(map(str, A)))

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from itertools import accumulate

def resolve():
    it = map(int, sys.stdin.read().split())
    N, K = next(it), next(it)
    A = [next(it) for i in range(N)]

    for k in range(K):
        B = [0]*(N+1)
        for i, di in enumerate(A):
            lhs = max(0, i-di)
            rhs = min(i+di+1, N)

            B[lhs] += 1
            B[rhs] -= 1

        if B[0] == N:
            print(*[N]*N)
            return
        A = accumulate(B)

    print(*list(A)[:-1])

if __name__ == "__main__":
    resolve()

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

cnt = 0
flg = True
while flg and cnt < k:
    res = [0 for _ in range(n)]
    for i in range(n):
        if i - a[i] < 0:
            res[0] += 1
        else:
            res[i-a[i]] += 1

        if i + a[i] + 1 < n:
            res[i+a[i]+1] -= 1

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

    if all(res[i] == n for i in range(n)):
        flg = False

    cnt += 1
    a = res.copy()

print(*a)

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


@njit
def solve(n, k, a):
    for _ in range(min(k, 41)):
        diff = np.zeros(3 * n + 1, dtype=np.int64)
        for pos in range(n):
            diff[n + pos - a[pos]] += 1
            diff[n + pos + a[pos] + 1] -= 1
        diff = diff.cumsum()
        a = diff[n:2 * n]
    return a


n, k = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int64)
a = solve(n, k, a)
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):
            if a[j]==0:
                l=j
                r=min(j+1,n)
                
                x[l]+=1
                if r!=n:
                
                    x[r]+=-1
                
            else:
                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):
from itertools import accumulate

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

for _ in range(K):
    if A == [N] * N:
        break
    B = [0] * (N+1)
    for i, a in enumerate(A):
        start = max(0, i - a)
        end = min(N-1, i + a) + 1
        B[start] += 1
        B[end] -= 1
    A = list(accumulate(B))[:-1]
print(' '.join(map(str, A)))

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

from itertools import accumulate
for i in range(min(k,100)):
  l=[0]*(n+2)
  for j in range(n):
    left=max(0,j-a[j])
    right=min(n,j+a[j])
    l[left]+=1
    l[right+1]-=1
  s=list(accumulate(l))
  
  a=s[:n]
print(*a)

Solution (Python):


import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, K, *A = map(int, read().split())

for _ in range(min(K, 42)):
    acc = [0] * (N + 1)
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N, i + a + 1)
        acc[l] += 1
        acc[r] -= 1
    acc[0] = min(N, acc[0])
    for i in range(N):
        acc[i + 1] = min(N, acc[i] + acc[i + 1])
    A = acc[:-1]
    if all(a == N for a in A):
        break
print(*A)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(min(K,100)):
    imos = [0]*(N+1)
    for i, ai in enumerate(A):
        imos[max(0, i-ai)] += 1
        imos[min(N, i+ai+1)] -= 1
    A = [imos[0]]
    for i in range(1, N):
        A += [imos[i]+A[i-1]]
print(' '.join(map(str, A)))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, K = map(int, rl().split())
    A = list(map(int, rl().split()))
    
    for _ in range(min(K, 100)):
        imos = [0] * N
        for i in range(N):
            left = max(0, i - A[i])
            right = min(N - 1, i + A[i])
            imos[left] += 1
            if right < N - 1:
                imos[right + 1] -= 1
        for i in range(1, N):
            imos[i] += imos[i - 1]
        A = imos[:]
    print(*A)


if __name__ == '__main__':
    solve()

Solution (Python):
n,k=map(int,input().split())
A=list(map(int,input().split()))
C=[n for i in range(n)]

for m in range(k):
    B=[0 for _ in range(n)]
    for i in range(n):
        l,r=max(0,i-A[i]),min(n-1,i+A[i])
        B[l] +=1
        if r+1<n:B[r+1] -=1
    for i in range(n-1):
        B[i+1]=B[i]+B[i+1]
    A=B
    if A==C:break
print(*A)