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 bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	N,K = inputMap()
	A = inputList()

	if N <= 2*K:
		T = [N for i in range(N)]
		print(*T)
		sys.exit()

	for j in range(K):
		T = [0 for i in range(N)]
		for i,val in enumerate(A):
			
			tmp_min = max(0,i-val)
			T[tmp_min] += 1

			if i+val+1 > N-1:
				continue
			tmp_max = min(N-1,i+val+1)
			T[tmp_max] -= 1

		for i,val in enumerate(T):
			if i == 0:
				continue
			T[i] += T[i-1]
		A = T

	print(*A)


if __name__ == "__main__":
	main()

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *













































def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	N,K = inputMap()
	A = inputList()

	if N <= 2*K:
		T = [N for i in range(N)]
		print(*T)
		sys.exit()

	for j in range(K):
		T = [0 for i in range(N)]
		for i,val in enumerate(A):
			
			tmp_min = max(0,i-val)
			T[tmp_min] += 1

			if i+val+1 > N-1:
				continue
			tmp_max = min(N-1,i+val+1)
			T[tmp_max] -= 1

		for i,val in enumerate(T):
			if i == 0:
				continue
			T[i] += T[i-1]
		A = T

	print(*A)



def segfunc(x, y):
    return 0

ide_ele = float('inf')

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res




def bisect_left_reverse(a, x):
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

def bisect_right_reverse(a, x):
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok





def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return None




def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)




def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y




def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv



def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)



if __name__ == "__main__":
	main()

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
b = [0 for i in range(N+2)]
if K > 70:
    ans = [N for i in range(N)]
    print(*ans)
else:
    for _ in range(K):
        for i in range(N+2):
            b[i] = 0
        for i in range(N):
            b[max(0, i+1-A[i])] += 1
            b[min(N+1, i+1+A[i]+1)] -= 1
        for i in range(1, N+1):
            b[i] += b[i-1]
            A[i-1] = b[i]
    print(*A)

Solution (Python):
n,k = map(int,input().split())
A = list(map(int,input().split()))
if n == 1:
    print(1)
else:
    for _ in range(k):
        flag = 0
        imos = [0]*(n+1)
        for i,a in enumerate(A):
            imos[max(0,i-a)] += 1
            imos[min(n,i+a+1)] -= 1
        flag = (imos[0] != n)
        for i in range(n-1):
            imos[i+1] += imos[i]
            if imos[i+1] != n:
                flag = 1
        A = imos[:n].copy()
        if not flag:break
    print(' '.join(str(i) for i in A))

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

for i in range(k):
	im = [0 for _ in range(n+1)]
	for i, x in enumerate(a):
		im[max(i-x, 0)] += 1
		im[min(i+x+1, n)] -= 1
	nxt = [im[0]]
	for i in range(1, n):
		nxt.append(nxt[-1] + im[i])
	a = nxt
	if min(a) == n:
		break

print(*a)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(K):
        start = [0] * N
        end = [0] * N
        for j in range(N):
            if j - A[j] < 0:
                start[0] += 1
            else:
                start[j-A[j]] += 1
            if j + A[j] >= N:
                pass
            else:
                end[j+A[j]] += 1
        tmp = start[0]
        A[0] = tmp
        tmp_min = tmp
        for j in range(1, N):
            tmp += start[j]
            tmp -= end[j-1]
            A[j] = tmp
            tmp_min = min(tmp_min, tmp)
        if tmp_min >= N:
            break
    print(" ".join(map(str, A)))

if __name__ == '__main__':
    main()

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

def main():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    
    if (k>50):
        ans = [n]*n
        print(*ans)
        exit()
    
    for i in range(k):
        b = [0]*n
        for i in range(n):
            l = i-a[i]
            r = i+a[i]
            
            b[max(l,0)] += 1
            if (r<n-1):
                b[r+1] -= 1
            
    
        for i in range(1,n):
            b[i] = b[i-1] + b[i]
        a = b
        
    print(*b)
    
    
if __name__=="__main__":
    main()

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

N, K = MAP()
A = LIST()
for cnt in range(K):
	tmp = [0]*(N+1)

	for i, a in enumerate(A):
		tmp[max(0, i-a)] += 1
		tmp[min(N, i+a+1)] -= 1
	tmp = list(accumulate(tmp))
	A = tmp[:-1]
	if all(x==N for x in A):
		break

print(*A)

Solution (Python):

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

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

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

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

Solution (Python):
from itertools import accumulate


def main():
    n, k = map(int, input().split())
    a = [int(i) for i in input().split()]
    ini = [0] * n
    fin = [n] * n
    for c in range(min(k, 45)):
        b = ini.copy()
        for i, ai in enumerate(a):
            b[max(i - ai, 0)] += 1
            if i + ai + 1 < n:
                b[i + ai + 1] -= 1
        a = list(accumulate(b))
    print(*a)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().rstrip()

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

    for _ in range(K):
        new_A = [0] * (N)
        for i, a in enumerate(A):
            s = i - a
            if s < 0:
                s = 0
            f = i + a + 1
            new_A[s] += 1
            if f < N:
                new_A[f] -= 1
        A = list(accumulate(new_A))
        if min(A) == N:
            break
    print(*A)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
Z=[n]*n
class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)
for _ in range(k):
    tree = BIT(n)
    for i in range(n):
        l = max(0,i-A[i])
        r = min(n,i+A[i]+1)
        
        tree.add(l,r,1)
        
    A=[tree.get_val(i) for i in range(n)]
    
    if A == Z:
        break
        
print(*A)

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


def query(lamps):
    start_list = []
    end_list = []
    for idx, power in enumerate(lamps):
        start, end = idx - power, idx + power
        start_list.append(start)
        end_list.append(end)

    start_list.sort(reverse=True)
    end_list.sort(reverse=True)

    now = 0
    for idx in range(n):
        while start_list and start_list[-1] <= idx:
            start_list.pop()
            now += 1

        while end_list and end_list[-1] < idx:
            end_list.pop()
            now -= 1

        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 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):
from sys import stdin
from itertools import accumulate
def main():
    
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=list(map(int,readline().split()))

    cnt=0
    while cnt<k:
        s=[0]*n
        for i in range(n):
            x_min=i-a[i]
            x_max=i+a[i]+1
            s[max(0,x_min)]+=1
            if n-1<x_max:
                pass
            else:
                s[x_max]-=1
        a=list(accumulate(s))
        cnt+=1
        
        flag=True
        for i in range(n):
            if a[i]!=n:
                flag=False
                break
        if flag: break

    print(*a)

if __name__=="__main__":
    main()

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

for _ in range(k):
    f = 1
    for i in range(1, n+1):
        if a[i] != n:
            f = 0
            break
    if f:
        break
    memo = [0] * (n+1)
    for i in range(1, n+1):
        l = max(1, i-a[i])
        r = min(n, i+a[i])
        memo[l-1] += 1
        memo[r] += -1
    b = [0]
    for memoi in memo:
        b.append(b[-1]+memoi)
    a = b

print(" ".join(list(map(str, a[1:n+1]))))

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

while(True):
    p = 0
    T = [0]*N
    for i in range(N):
        T[max(i-A[i], 0)] += 1
        if i+A[i]+1 > N - 1:
            pass
        else:
            T[i+A[i]+1] -= 1
    for i in range(1,N):
        T[i] += T[i-1]
    c += 1
    if c == K:
        for i in range(N):
            print(T[i], end=" ")
        sys.exit()
    for i in range(N):
        if T[i] < N:
            p = 1
            break
    if p == 0:
        for i in range(N):
            print(N, end= " ")
        sys.exit()
    A = T[:]

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





cnt = 0
while (A[0] < N or A[-1] < N) and cnt < K:
    cnt += 1
    next_A = [0] * (N+1)
    for j in range(N):
        tmp = A[j]
        next_A[max(j-tmp, 0)] += 1
        next_A[min(N, tmp+1+j)] -= 1
    for j in range(N):
        next_A[j+1] += next_A[j]
    next_A.pop()
    A = next_A
print(" ".join([str(i) for i in A]))

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


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

    
    
    
    while k:
        lst=[1]*n
        dic={}
        cnt=0
        for i in range(n):
            lst[i]+=cnt
            if i in dic:
                cnt-=dic[i]
            if a[i]>0:
                if not i+a[i] in dic:
                    dic[i+a[i]]=1
                else:
                    dic[i+a[i]]+=1
                cnt+=1

        dic={}
        cnt=0
        for i in range(n)[::-1]:
            lst[i]+=cnt
            if i in dic:
                cnt-=dic[i]
            if a[i]>0:
                if not i-a[i] in dic:
                    dic[i-a[i]]=1
                else:
                    dic[i-a[i]]+=1
                cnt+=1
        k-=1
        if sum(lst)==n*n:
            break
        
        a=lst[:]

    print(*lst)

main()

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    if K >= 50: A = [N] * N
    else:
        for k in range(K):
            nextL = [0] * (N + 1)
            for i, a in enumerate(A):
               left = max(0, i - a)
               right = min(N, i + a + 1)
               nextL[left] += 1
               nextL[right] -= 1
            A[0] = nextL[0]
            for i in range(1, N):
                A[i] = A[i-1] + nextL[i]
    print(*A, sep=" ")
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):

import sys
import copy

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,k = na()
    a = na()
    memo = [0]*(n+1)
    for i in range(n):
        ai = a[i]
        memo[max(0, i-ai)] += 1
        memo[min(n, i+ai+1)] -= 1
    k -= 1
    if k == 0:
        tmp = 0
        for i in range(n):
            tmp += memo[i]
            print(tmp, end=' ')
        return
    while k != 0:
        flag = 0
        memo2 = [0]*(n+1)
        tmp = 0
        for i in range(n+1):
            tmp += memo[i]
            if tmp >= max(i, n-i-1):
                flag += 1
            memo2[max(0, i-tmp)] += 1
            memo2[min(n, i+tmp+1)] -= 1
        if flag == n:
            memo2[0] = n
            memo2[-1] = -1*n
            break
        memo = copy.copy(memo2)
        k -= 1
    tmp = 0
    for i in range(n):
        tmp += memo2[i]
        print(tmp, end=' ')
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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



    xxxx = 0
    while True:
        xxxx += 1
        imos = [0] * (N + 2)
        if xxxx == 100 or xxxx == K + 1:
            break
        for i, a in enumerate(A):
            imos[max(0, i + 1 - a)] += 1
            imos[min(N + 1, i + 1 + a + 1)] -= 1

        ruiseki = [0] * (N + 2)
        for i in range(N + 2):
            ruiseki[i] = imos[i] + ruiseki[i - 1]

        for i, v in enumerate(ruiseki[1:N + 1]):
            A[i] = v

    print(*ruiseki[1:N + 1])



if __name__ == '__main__':
    main()

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

for i in range(K):
    a=[0 for i in range(N+1)]
    for j in range(N):
        a[max(0,j-L1[j])]+=1
        a[min(N,j+L1[j]+1)]-=1
        
    L2=[a[0]]
    for j in range(1,N):
        L2.append(L2[-1]+a[j])
    
    if L2==L1[:N]:
        print(*L2)
        exit()
    else:
        L1=L2+[0]
print(*L2)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    sa = sum(a)
    for i in range(k):
        mov = [0]*n
        for i,ai in enumerate(a):
            if i-ai >= 0:
                mov[i-ai] += 1
            else:
                mov[0] += 1
            if i+ai+1 < n:
                mov[i+ai+1] -= 1
        na = a*1
        sna = sa
        a[0] = mov[0]
        sa = mov[0]
        for i in range(1,n):
            a[i] = a[i-1]+mov[i]
            sa += a[i]
        if sna == sa:
            break
    print(" ".join(map(str,a)))

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s_readline = sys.stdin.readline


def solve():

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

    
    

    for k in range(K):

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

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

        A = B

        if s == N * N:
            print(' '.join(map(str, A)))
            exit()

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


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
n,k=map(int,input().split())
m1=list(map(int,input().split()))
m2=[]
imos=[0]*(n+1)
counter=0
while counter<=k:
  counter+=1
  if counter%2==1:
    m2=[]
    imos=[0]*(n+1)
    for i in range(n):
      imos[max(0,i-m1[i])]+=1
      imos[min(n,i+m1[i]+1)]-=1
    current=0
    for i in range(n):
      current+=imos[i]
      m2.append(current)
    sameflag=1
    for i in range(n):
      if m1[i]!=m2[i]:
        sameflag=0
        break
    if sameflag==1:
      for i in range(n):
        m2[i]=str(m1[i])
      print(' '.join(m2))
      sys.exit()
  else:
    m1=[]
    imos=[0]*(n+1)
    for i in range(n):
      imos[max(0,i-m2[i])]+=1
      imos[min(n,i+m2[i]+1)]-=1
    current=0
    for i in range(n):
      current+=imos[i]
      m1.append(current)
    for i in range(n):
      if m1[i]!=m2[i]:
        sameflag=0
        break
    if sameflag==1:
      for i in range(n):
        m2[i]=str(m1[i])
      print(' '.join(m2))
      sys.exit()
if k%2==0:
  for i in range(n):
    m2[i]=str(m1[i])
  print(' '.join(m2))
else:
  for i in range(n):
    m1[i]=str(m2[i])
  print(' '.join(m1))

Solution (Python):
n, k = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0


while True:
    cnt += 1
    new = [0 for _ in range(n)]
    for i in range(n):
        new[max(0, i-arr[i])] += 1

        tmp = i+arr[i]+1
        if tmp < n:
            new[tmp] -= 1

    flag = 1
    for i in range(1, n):
        new[i] += new[i-1]
        if new[i] < n:
            flag = 0

    arr = new
    
    if flag or cnt >= k:
        break

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

Solution (Python):


from itertools import accumulate
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]+1<n:
            b[i+a[i]+1]-=1
    a=list(accumulate(b))
    if a==[n]*n:
        break
    
print(" ".join(map(str,a)))

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

N,K = map(int,readline().split())
A = list(map(int,readline().split()))
def calc(A):
    B = [0] * len(A)
    for i in range(len(A)):
        B[max(0,i - A[i])] += 1
        if i + A[i] + 1 < len(A):
            B[i + A[i] + 1] -= 1
    for i in range(1,len(B)):
        B[i] = B[i - 1] + B[i]
    return B

for i in range(K):
  A = calc(A)
  if len(set(A)) == 1 and A[0] == N:
    print(*A)
    break
else:
  print(*A)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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


for i in range(K):
    nxtA = [0]*N
    imos_l = [0]*N
    imos_r = [0]*N

    for j in range(N):
        if A[j]>0:
            if j+1<N:
                imos_l[j+1] += 1
            if j+1+A[j]<N:

                imos_l[j+1+A[j]] -= 1
    for j in reversed(range(N)):
        if A[j]>0:
            if j-1>=0:
                imos_r[j-1] += 1
            if j-1-A[j]>=0:
                imos_r[j-1-A[j]] -= 1
    cur = 1
    for j in range(N):
        cur += imos_l[j]
        nxtA[j] += cur
    cur = 0
    for j in reversed(range(N)):
        cur += imos_r[j]
        nxtA[j] += cur
    
    if sum(nxtA)==N*N:
        print(*nxtA)
        exit()
    if i<N-1:
        for j in range(N):
            A[j] = nxtA[j]

print(*nxtA)

Solution (Python):
n,k=map(int,input().split())
arr=list(map(int,input().split()))
for _ in range(min(200,k)):
  tmp=[0]*n
  for i in range(n):
    if i+1<n:
      tmp[i+1]+=1
      if i+arr[i]+1<n:
        tmp[i+arr[i]+1]+=-1
    if i-1>=0:
      tmp[i]+=-1
      if i-arr[i]>=0:
        tmp[i-arr[i]]+=1
      else:
        tmp[0]+=1
  for i in range(1,n):
    tmp[i]+=tmp[i-1]
  for i in range(n):
    tmp[i]+=1
  arr=tmp
print(*arr)

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

for _ in range(k):
    b = [0] * (n + 2)
    for i in range(n):
        b[max(0, i - a[i])] += 1
        b[min(n + 1, i + a[i] + 1)] -= 1
    a[0] = b[0]
    cnt = a[0]
    for i in range(1, n):
        a[i] = a[i - 1] + b[i]
        cnt += a[i]

    
    if cnt == n**2:
        break

print(*a)

Solution (Python):
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
if 2**(k)>=n**10:
    for i in range(n):
        print(n,end='')
        print(' ',end='')
else:
    for _ in range(k):
        sub=[0]*n
        for i in range(n):
            sub[max(0,i-a[i])]+=1
            if i+a[i]<n-1:
                sub[i+a[i]+1]-=1
        for i in range(1,n):
            sub[i]=sub[i]+sub[i-1]
        a=sub
    for i in sub:
        print(i,end='')
        print(' ',end='')

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

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

    for j in range(n):
        x = li[j]
        now[max(0,j-x)] += 1
        if j+x+1 < n:
            now[j+x+1] -= 1
    
    for j in range(n-1):
        now[j+1] += now[j]

    li = now
    if min(li) >= n:
        break

print(*li)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
now = list(mapint())
from itertools import accumulate
iteration = min(N.bit_length()*4, K)
for k in range(iteration):
    nx = [0]*N
    for i, a in enumerate(now):
        nx[max(0, i-a)] += 1
        if i+a+1<N:
            nx[i+a+1] -= 1
    nx = list(accumulate(nx))
    now = nx[:]
print(*now)

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


for k in range(K):
    imos = [0] * (N+1)
    for n in range(N):
        a = n - A[n]
        b = n + A[n]
        a = max(0,a)
        b = min(N-1,b)
        imos[a] += 1
        imos[b+1] -= 1
    csum = list(itertools.accumulate(imos))
    A = csum[:-1]
A = [str(a) for a in A]
print (' '.join(A))

Solution (Python):





import math
import sys
import bisect
import heapq  
import collections
from collections import deque
import pprint

inf = 10**18
mod = 10**9+7

n,k = map(int, input().split())
b = list(map(int, input().split()))
a = [0]
for i in b:
    a.append(i)

flag = False
while k > 0 and (not flag):
    flag = True
    a2 = [0 for i in range(n+1)]
    for i,num in enumerate(a[1:]):
        l = max(i-num,0)
        r = min(i+num,n-1)
        l+=1
        r+=1
        a2[l] += 1
        if r+1 != n+1:
            a2[r+1] -= 1

    a = [0 for i in range(n+1)]
    for i in range(1, n+1):
        a[i] += a[i-1] + a2[i]
        if a[i] != n:
            flag=False
    k-=1
if flag:
    print(*[n for i in range(n)], sep=' ')
else:
    print(*a[1:], sep=' ')

Solution (Python):

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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


def func(A):
    
    
    all_N = True
    aA = [0]*(2*N+10)
    for i, a in enu(A):
        if a != N:
            all_N = False
        st = max(0, 2*i-2*a-1)
        en = min(2*N, 2*i+2*a+1)
        aA[st] += 1
        aA[en] -= 1

    
    for i in range(2*N):
        aA[i+1] += aA[i]

    

    res = [val for i, val in enu(aA) if i%2==0]
    res = res[:N]
    
    return res, all_N

for _ in range(K):
    A, all_N = func(A)
    if all_N:
        break
    

print(*A)

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

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


if __name__ == '__main__':
    main()

Solution (Python):
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
for _ in range(k):
    c = [0] * n
    for i in range(n):
        c[max(0, i-a[i])] += 1
        if a[i] + i + 1 < n:
            c[a[i] + i + 1] -= 1
    j = 0
    for i in range(n):
        j += c[i]
        a[i] = j

    if sum(a) == n * n:
        print(*([n] * n))
        break
else:
    print(*a)