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):
from itertools import accumulate

def solve(x,K):
    N = len(x)
    def transform(x):
        t = [0]*(N+1)
        for i,v in enumerate(x):
            t[max(i-v,0)] += 1
            t[min(i+v+1,N)] -= 1
        return tuple(v for v,_ in zip(accumulate(t),range(N)))

    for i in range(K):
        y = transform(x)
        if x == y:
            break
        x = y
    return x,i
from random import randrange
if __name__ == '__main__':
    N,K = map(int,input().split())
    x = tuple(map(int,input().split()))
    res, i = solve(x,K)
    print(*res)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def solve():
    n, k = LI()
    a = LI()
    for i in range(k):
        bit = [0] * (n+1)
        for j in range(n):
            bit[max(0, j - a[j])] += 1
            bit[min(n, j + a[j] + 1)] -= 1
        f = 0
        bit = list(itertools.accumulate(bit))
        for j in range(n):
            a[j] = bit[j]
            if a[j] < n:
                f = 1
        if f:
            continue
        break
    print(*a)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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



for k in range(K):
    lst = [0] * (N + 1)
    for i, a in enumerate(A):
        left = max(i - a, 0)
        right = min(N - 1, i + a)
        lst[left] += 1
        lst[right + 1] -= 1
    tmp = 0
    for i in range(N):
        tmp += lst[i]
        A[i] = tmp

    flag = 1
    for i in range(N):
        if A[i] != N:
            flag = 0
            break

    if flag:
        print(*([N] * N))
        exit()

print(*A)

Solution (Python):
n,k,*a,=map(int,open(0).read().split())
def f(li):
	b=[0]*(n+1)
	for i,x in enumerate(li):
		b[max(0,i-x)]+=1
		b[min(i+x+1,n)]-=1
	for i in range(n):
		b[i+1]+=b[i]
	return b[:-1]
for _ in range(k):
	a=f(a)
	if a==[n]*n:
		print(*a)
		exit()
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):
        B=[0]*(n+1)
        for j in range(n):
            a=A[j]
            B[max(0,j-a)]+=1
            B[min(n,j+a+1)]-=1
        for j in range(n):
            B[j+1]+=B[j]
        A=B.copy()
        if sum(A[:-1])==n**2:
            break
    print(*A[:-1])
if __name__ == '__main__':
    main()

Solution (Python):


from itertools import accumulate
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    for i in range(K):
        B = [0]*(N+1)
        for j in range(N):
            d = A[j]
            x = j-d
            y = j+d
            if x < 0:
                B[0] += 1
            else:
                B[x] += 1
            if N-1 < y:
                B[N] -= 1
            else:
                B[y+1] -= 1
        A = list( accumulate(B))
        check = True
        for j in range(N):
            if A[j] < N:
                check = False
        if check:
            break
    print(" ".join( map(str, A[:-1])))
            
if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n,k=NM()
l=L()
dp=[]
from itertools import accumulate
for _ in range(min(100,k)):
    tl,l=l,[0]*(n+1)
    for i,j in enumerate(tl):
        l[max(0,i-j)]+=1
        l[min(n,i+j+1)]-=1
    l=list(accumulate(l))
print(" ".join(map(str,l[:n])))

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
def move():
    global a
    s = [0] * (n + 1)
    for i in range(n):
        s[max(0, i - a[i])] += 1
        s[min(n, i + a[i] + 1)] -= 1
    for i in range(1, n + 1):
        s[i] += s[i - 1]
    if all(map(lambda i: a[i] == s[i], range(n))):
        return True
    a = s
    return False
for _ in range(k):
    if move():
        break
print(*a[:n])

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(K):
  imos = [0] * (N + 1)
  for i in range(N):
    l = max(0, i - a[i])
    r = min(N - 1, i + a[i]) + 1
    imos[l] += 1
    imos[r] -= 1
  for i in range(N): imos[i + 1] += imos[i]
  a = imos[: -1]
  if a.count(N) == N: break
print(*a)

Solution (Python):
from collections import *
from math import *
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
b = [0 for i in range(n+1)]
cnt = 0
for i in range(k):
	b = [0 for i in range(n+1)]
	for i in range(n):
		ub = min(n,i+a[i]+1)
		lb = max(0,i-a[i])
		b[lb] += 1
		b[ub] -= 1
	for i in range(1,n):
		b[i] += b[i-1]
	a = b[::]
	a.pop()
	if(sum(a) == n*n):
		break
print(*a)

Solution (Python):
import sys

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

def solve():
    n, k = nm()
    if k > 45:
        k = 45
    a = nl()
    b = [0]*n
    for _ in range(k):
        for i in range(n):
            b[max(0, i - a[i])] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        for i in range(n-1):
            b[i+1] += b[i]
            a[i] = 0
        a[-1] = 0
        b, a = a, b
    print(*a)
    return

solve()

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
imos = [0 for _ in range(n+1)]
"""
座標xに光の強さdの電球→[x-d, x+d] てらす
強さ0でもそれには適用.
"""
for _ in range(k):
	imos = [0 for _ in range(n+1)]
	for i in range(n):
		imos[max(i-a[i], 0)] += 1
		imos[min(i+a[i]+1, n)] -= 1
	cnt = 0
	alln = 0
	for i in range(n):
		cnt += imos[i]
		a[i] = cnt
		if a[i] == n:
			alln += 1
	if alln == n:
		break
print(*a)

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

for i in range(k):
    if a == [n] * n:
        break
    else:
        a2 = [0] * (n + 1)
        for j in range(n):
            temp = a[j]
            a2[max(j - temp, 0)] += 1
            a2[min(j + temp + 1, n)] -= 1
        a3 = [0]
        for j in range(n):
            a3.append(a3[-1] + a2[j])
        a = a3[1:]
for i in range(n):
    print(a[i], end = " ")
print()

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

M=[N]*N

for i in range(K):
    L=[0]*(N+1)
    for j in range(N):
        L[max(0,j-A[j])]+=1
        L[min(N,j+A[j]+1)]-=1
        
    S=0
    for j in range(N):
        S+=L[j]
        A[j]=S

    if A==M:
        break

for i in range(N):
    print(A[i],end=" ")
print()

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

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

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

print(*A)

Solution (Python):
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


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


def test(A, K):
    A = list(A)
    for _ in range(K):
        B = [0] * N
        for i in range(N):
            b = 0
            for j in range(N):
                if A[j] >= abs(j - i):
                    b += 1
            B[i] = b
        A = B
    print(*A)
    return A


def test2(A, K):
    A = list(A)
    for _ in range(K):
        B = [0] * N
        for i in range(N):
            for j in range(N):
                if A[i] >= abs(j - i):
                    B[j] += 1
        A = B
    print(*A)
    return A


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


def solve(A, K):
    prev = A
    for _ in range(K):
        imos = [0] * (N + 1)
        for i in range(N):
            imos[max(0, i - A[i])] += 1
            imos[min(N, i + A[i] + 1)] -= 1
        prev = A
        A = cumsum(imos)[:-1]
        if prev == A:
            break
    print(*A)








solve(A, K)

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 i in range(K):
    diff = [0] * (N+2)
    for n, a in enumerate(A):
        n += 1
        l = max(1,n-a)
        r = min(N+1,n+a+1)
        diff[l] += 1
        diff[r] -= 1
    B = [0]
    for d in diff:
        B.append(B[-1] + d)
    A = B[2:-1]
    if sum(A) == N * N:
        break

print(*A)

Solution (Python):
N, K = map(int, input().split())
A = [int(a) for a in input().split()]

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    s = [0]*n
    for i,d in enumerate(a):
        if d==0:
            s[i] += 1
            if i+1<=n-1:
                s[i+1] -= 1
        else:
            s[max(0,i-d)] += 1
            if i+d+1<=n-1:
                s[min(n-1, i+d+1)] -= 1
    ss = [0]*n
    tmp = 0
    for i,num in enumerate(s):
        tmp += num
        ss[i] = tmp
    if all(t==v for t,v in zip(a,ss)):
        break
    a = ss
    
write(" ".join(map(str, a)))

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

for _ in range(k):
  last = now
  now = []
  imos = [0 for _ in range(n+1)]
  for i in range(n):
    l = max(0,i-last[i])
    r = min(n,i+last[i]+1)
    imos[l] += 1
    imos[r] -= 1
  now.append(imos[0])
  for i in range(1,n):
    now.append(now[-1]+imos[i])
  
  if sum(now) == n**2:
    print(' '.join(map(str,now)))
    exit()
print(' '.join(map(str,now)))

Solution (Python):
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,k=MI()
    a=LI()
    for _ in range(k):
        na=[0]*(n+1)
        for i in range(n):
            l=max(0,i-a[i])
            r=min(n,i+a[i]+1)
            na[l]+=1
            na[r]-=1
        if na[0]==n and na[-1]==-n:
            a=[n]*n
            break
        for i in range(n):
            na[i+1]+=na[i]
        a=na
    print(*a[:n])

main()

Solution (Python):
from heapq import heappush, heappop

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

while K and sum(A) < N * N :
  l = [0] * N
  h = []
  for i in range(N) :
    while h and h[0] < i :
      heappop(h)
    l[i] = len(h)
    heappush(h, (i + A[i]))
    
  r = [0] * N
  h = []
  for i in range(N - 1, -1, -1) :
    while h and h[0] < -i :
      heappop(h)
    r[i] = len(h)
    heappush(h, (-(i - A[i])))
    
  for i in range(N) :
    A[i] = l[i] + r[i] + 1
    
  K -= 1
  
print(*A)

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

for _ in range(K):
    A_old = A
    A = [0] * (N)
    for idx_A, a in enumerate(A_old):
        A[max(0, idx_A-a)] += 1
        if idx_A+a+1 < N:
            A[idx_A+a+1] -= 1
    for idx_A in range(1, N):
        A[idx_A] += A[idx_A-1]
    if A_old == A:
        break
print(" ".join(map(str, A)))

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

from decimal import *
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n, k = MAP()
a = LIST()
for j in range(k):
    prea = [i for i in a]
    num = [0 for _ in range(n + 2)]
    for i in range(n):
        l = max(1, i + 1 - a[i])
        r = min(n + 1, i + 1 + a[i] + 1)
        num[l] += 1
        num[r] -= 1
    for i in range(1, n + 2):
        num[i] += num[i - 1]
    
    a = [i for i in num[1:n + 1]]
    if a == prea:
        break
a = [str(i) for i in a]
print(' '.join(a))

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k,*a = map(int,read().split())

from itertools import accumulate

if k >= 100:
    print(*[n]*n)

else:
    for _ in range(k):
        na = [0]*n
        for i,ai in enumerate(a):
            na[max(0,i-ai)] += 1
            if i+ai+1 < n:
                na[i+ai+1] -= 1
        a = accumulate(na)

    print(*list(a))

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

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

K = min(100, K)
while K:
    K -= 1
    table = [0]*(N+1)
    for i in range(N):
        a = A[i]
        table[max(0, i-a)] += 1
        table[min(N, i+a+1)] -= 1
    
    for i in range(1, N):
        table[i] += table[i-1]
    
    A = table[:-1]

print(*A)

Solution (Python):
import sys
from itertools import accumulate

n, k, *aaa = map(int, sys.stdin.buffer.read().split())

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

    aaa = list(accumulate(bbb))
    aaa.pop()

    if all(a == n for a in aaa):
        break

print(*aaa)

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

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

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

    A=list(accumulate(B))
    flag=1
    for i in range(N):
        if A[i]<N:
            flag=0
        A[i]=min(A[i],N)

    if flag:
        break
    

print(*A[:N])

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

if k > 200:
    k = 200

for i in range(k):
    new = [0] * n
    diff = [0] * n
    
    for j in range(n):
        diff[max(0, j - a[j])] += 1
        if j + a[j] + 1 < n:
            diff[j + a[j] + 1] -= 1

    for j in range(n):
        new[j] = diff[j] + new[j - 1]
    
    a = new
    
print(' '.join(map(str,a)))

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(k):
    b = [0] * (n + 1)
    for i in range(n):
        b[max(0, i - a[i])] += 1
        b[min(n, i + a[i] + 1)] -= 1
    for i in range(n):
        b[i + 1] += b[i]
    a = b[:-1].copy()
    for x in a:
        if x < n:
            break
    else:
        print(*a)
        exit(0)
print(*a)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
lsn = a[:]
for _ in range(k):
  lsc = lsn[:]
  lsn = [0]*(n+1)
  for i in range(n):
    x = lsc[i]
    lsn[max(0,i-x)] += 1
    lsn[min(n,i+x+1)] -= 1
  for i in range(1,n+1):
    lsn[i] += lsn[i-1]
  if lsn.count(n) == n:
    break
print(*lsn[:n])

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

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

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

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

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


if __name__ == '__main__':
    main()