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 numba import jit


@jit
def solve(N, K, A):
    for _ in range(K):
        imos = [0] * (N+1)
        for i in range(N):
            left = max(0, i-A[i])
            right = min(N-1, i+A[i])+1
            imos[left] += 1
            imos[right] += -1

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

        if A == next_A:
            return A
        A = next_A
    return A


N, K = map(int, input().split())
A = [int(x) for x in input().split()]
print(" ".join([str(x) for x in solve(N, K, 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):
    t = a[i]
    B[max(i-t,0)] +=1
    B[min(i+t+1,N)] -=1
  for i in range(N):
    B[i+1] += B[i]
  a=B[:N]        
  if min(a)==N:
    break
print(*a)

Solution (Python):
N, K= map(int,input().split())
A = list(map(int,input().split()))
a=A[:]
for _ in range(K):
  B=[0]*(N+1)
  for i in range(N):
    t = a[i]
    B[max(i-t,0)] +=1
    B[min(i+t+1,N)] -=1
  for i in range(N):
    B[i+1] += B[i]
  a=B[:N]        
  if min(a)==N:
    break
print(*a)

Solution (Python):
from numba import jit

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

    for j in range(N - 1):
      B[j + 1] += B[j]
  
    if A == B:
      return B
    A = B
  return B
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = solve(N, K, A)
for b in B:
  print(b, end=" ")

Solution (Python):
import numpy as np

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

from numba import jit

@jit
def imos(x):
  global N
  B = np.zeros_like(x)
  for i in range(N):
    p = x[i]
    L = max(i-p, 0)
    R = min(i+p, N-1)
    B[L] += 1
    if R < N-1:
      B[R+1] -= 1
  B = np.cumsum(B)
  return B

for i in range(K):
  if i >= 50:
    break
  A = imos(A)

print(*A)

Solution (Python):
n,k_ = map(int,input().split())
a_li = list(map(int,input().split()))
a_li_o = [0]*n
for i in range(k_):
    for l in range(n):
        a_li_o[l] = a_li[l]
    dum_li = [0]*n
    for j in range(n):
        left = j - a_li[j]
        right = j + a_li[j] + 1
        if left < 0:
            left = 0
        dum_li[left] += 1
        if right > n-1:
            continue
        dum_li[right] -= 1
    total = 0
    for k in range(n):
        total += dum_li[k]
        dum_li[k] = total
    for k in range(n):
        a_li[k] = dum_li[k]
    if a_li_o == a_li:
        break
print(" ".join(map(str,a_li)))

Solution (Python):
def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  n = len(a)
  for i in range(n):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < n:
      ret[end+1] -= 1
  for i in range(1,n):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if sum(num_light) == n**2:
    break
    
print(*num_light)

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

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  for i in range(1,N):
    D[i]+=D[i-1]
  A=D[:-1]
  return A 

for i in range(min(K,42)):
  A=f(A)
print(*A)

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

for i in range(min(41, k)):
    t = [0] * (n+1)
    for j in range(n):
        t[max(0, j-a[j])] += 1
        t[min(j+a[j]+1, n)] -= 1

    for j in range(1, n):
        t[j] += t[j-1]
    a = t[:n]

print(*a)

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

    Z = [N]*N

    while K > 0 and A != Z:
        K-=1
        B = [int(0)]*(N+1)
        for i in range(N):
            B[max(int(0),i-A[i])]+=1
            B[min(N-1,i+A[i])+1]-=1
        for i in range(1,N):
            B[i]+=B[i-1]

        A = B[0:N]

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

if __name__ == '__main__':
    main()

Solution (Python):






"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import os
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from io import BytesIO, IOBase
from typing import Dict, List, Optional, Set, Tuple


def solveFast(values: List[int], N: int, K: int) -> List[int]:
    result = [0] * N
    for v, i in sorted(((v, i) for i, v in enumerate(values)), reverse=True):
        v = max(v, K)
        for j in range(max(0, i - v), min(N, v + i + 1)):
            n = abs(j - i)
            if n == 0:
                result[j] += 1
            else:
                result[j] += n * (n + 1) // 2
    return result


def solve(values: List[int], N: int, K: int) -> List[int]:
    if K >= N - 1:
        return [N] * N
    for _k in range(K):
        prev = values.copy()
        values = [0] * N
        for i, v in enumerate(prev):
            l = max(0, i - v)
            r = min(N - 1, v + i)
            values[l] += 1
            if r < N - 1:
                values[r + 1] -= 1
        for i in range(1, N):
            values[i] += values[i - 1]
        if all(v == N for v in values):
            break
    return values


def do_job(stdin, stdout):
    "Do the work"
    LOG.debug("Start working")
    
    N, K = map(int, stdin.readline().split())
    values = list(map(int, stdin.readline().split()))
    
    
    
    result = solve(values, N, K)
    print(*result, file=stdout)


def print_output(testcase: int, result, stdout) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case 
    
    


BUFSIZE = 8192


class FastIO(IOBase):
    
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(IOWrapper(sys.stderr))
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None

if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    stdin = IOWrapper(sys.stdin)
    stdout = IOWrapper(sys.stdout)
    do_job(stdin, stdout)
    stdout.flush()
    for h in LOG.handlers:
        h.flush()
    return 0


if __name__ == "__main__":
    sys.exit(main())

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

for count in range(k):
    range_diff = [0] * n
    for pos in range(n):
        candidate_min = pos - a[pos]
        candidate_max = pos + a[pos] + 1
        if pos - a[pos] >= 0:
            min = pos - a[pos]
        else:
            min = 0
        range_diff[min] += 1
        if candidate_max <= n-1:
            range_diff[candidate_max] -= 1
    for i in range(1, n):
        range_diff[i] += range_diff[i-1]
    a = range_diff
    if count >= 43:
        break

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

Solution (Python):
import sys

def input():
    return sys.stdin.readline()[:-1]


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

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

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

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

@njit('i8,i8,i8[::1]',cache=True)
def solve(N,K,A):
    for i in range(K):
        br = np.zeros(N+1, dtype=np.int64)

        for ind, rux in enumerate(A):
            br[max(ind-rux,0)] += 1
            br[min(ind+rux+1,N)] -= 1
        A = br.cumsum()[:-1]

        if br[0] == N and br[-1] == -N:
            return A
    return A


if __name__ == "__main__":
    n,k = map(int, input().split())
    a = np.array(list(map(int, input().split())),dtype=np.int64)
    ans = solve(n,k,a)
    print(*ans)

Solution (Python):
from sys import stdin
import numpy as np
from numba import njit
def main():
    
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=np.array(list(map(int,readline().split())),dtype=np.int64)

    cnt=0
    while cnt<k:
        s=f(n,a)
        a=np.cumsum(s)
        cnt+=1
        if a[a==n].size==n:
            break

    print(*a)

@njit
def f(n,a):
    s=np.zeros(n,dtype=np.int64)
    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
    return s

if __name__=="__main__":
    main()

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

from itertools import accumulate

if K>=50:
    print(*[N]*N)
    exit()
    
for _ in range(K):
    ans=[0]*(N+1)
    for i,a in enumerate(A):
        ans[max(0,i-a)]+=1
        ans[min(i+a+1,N)]-=1
    A = list(accumulate(ans))[:-1]
    if all(i == N for i in A):
        break
print(*A)

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


@jit
def imo(a, n):
    imos = np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        imos[max(0, i-a[i])] += 1
        imos[min(n, i+a[i])+1] -= 1

    
    immo = np.zeros(n+1, dtype=np.int64)
    immo = np.cumsum(imos)

    return immo[:n]


for _ in range(min(K, 41)):
    A = imo(A, N)

print(*A)

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

from itertools import accumulate
    
for _ in range(K):
    ans=[0]*(N+1)
    for i,a in enumerate(A):
        ans[max(0,i-a)]+=1
        ans[min(i+a+1,N)]-=1
    A = list(accumulate(ans))[:-1]
    if all(i == N for i in A):
        break
print(*A)

Solution (Python):

import numpy as np
from numba import i8, njit


@njit(i8[:](i8, i8[:]), cache=True)
def f(k, A):
    n = len(A)
    cur = A
    for _ in range(k):
        prev = cur
        cur = np.zeros_like(A)
        for x, p in enumerate(prev):
            cur[max(0, x-p)] += 1
            if x+p+1 < n:
                cur[x+p+1] -= 1

        satulated = True
        for i in range(1, n):
            cur[i] += cur[i-1]
            satulated &= cur[i] == n
        if satulated:
            break
    return cur


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(tuple(map(int, args[1].split())))
    return ' '.join(map(str, f(k, A)))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

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


def read():
    N, K = map(int, input().strip().split())
    A = np.fromstring(input().strip(), dtype=np.int32, sep=" ")
    return N, K, A


@njit
def solve(N, K, A):
    d = np.empty(N+1, dtype=np.int32)

    for k in range(K):
        for i in range(N):
            d[i] = 0
        
        for i in range(N):
            l = max(0, i-A[i])
            r = min(N, i+1+A[i])
            d[l] += 1
            d[r] -= 1
        
        terminate = True
        v = 0
        for i in range(N):
            v += d[i]
            A[i] = v
            if terminate and A[i] < N:
                terminate = False
        if terminate:
            break
    return A


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    print(*outputs)

Solution (Python):

import numpy as np
from numba import b1, i8, njit, types


@njit(types.Tuple((i8[:], b1))(i8[:]), cache=True)
def f(A):
    n = len(A)
    ret = np.zeros_like(A)
    for x, p in enumerate(A):
        ret[max(0, x-p)] += 1
        if x+p+1 < n:
            ret[x+p+1] -= 1

    satulated = True
    for i in range(1, n):
        ret[i] += ret[i-1]
        satulated &= ret[i] == n
    return ret, satulated


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(tuple(map(int, args[1].split())))

    for _ in range(k):
        A, satulated = f(A)
        if satulated:
            break

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


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

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


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A):
    d = [0 for i in range(N+1)]

    for k in range(K):
        for i in range(N):
            d[i] = 0
        
        for i in range(N):
            l = max(0, i-A[i])
            r = min(N, i+1+A[i])
            d[l] += 1
            d[r] -= 1
        
        terminate = True
        v = 0
        for i in range(N):
            v += d[i]
            A[i] = v
            if terminate and A[i] < N:
                terminate = False
        if terminate:
            break         
    print(*[a for a in A])


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

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

def imos(a):
  imos_l=[0 for i in range(n)]

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

    imos_l[left]+=1
    if right+1!=n:
      imos_l[right+1]-=1

  b=[0]
  for i in range(1,n+1):
    b.append(b[i-1]+imos_l[i-1])

  return b[1:]

for i in range(k):
  a=imos(a)
  if a.count(n)==n:
    break

print(*a)

Solution (Python):
a,b=map(int,input().split())
l=list(map(int,input().split()))
import itertools
b=min(b,50)
def ku(l):
    y=[0]*a
    for j,x in enumerate(l):
      y[max(0,j-x)]+=1
      r=min(j+x,a-1)
      if r<a-1:
        y[r+1]-=1
    return itertools.accumulate(y)

  
for _ in range(b):
  l=ku(l)
print(*l)

Solution (Python):
N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
for k in range(K):
    B = [0] * (N+1)
    for i, a in enumerate(A):
        l = max(0, i-a)
        r = min(i+a+1, N)
        B[l] += 1
        B[r] -= 1
    for i in range(1, N+1):
        B[i] += B[i-1]
    B.pop()
    if (A==B): break
    A = B
for a in A:
    print(a, end=' ')
print()

Solution (Python):
import math
N,K = map(int,input().split())
A = list(map(int,input().split()))
for j in range(min(K,int(2*(math.log2(N)))+10)):
	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 < N-1:
			B[r+1] -= 1
	for i in range(1,N):
		B[i] += B[i-1]
	A = B
print(' '.join(map(str,A)))

Solution (Python):
from itertools import accumulate
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 = list(accumulate(b))
    if sum(a) == n ** 2:
        a.pop()
        print(*a)
        exit()

a.pop()
print(*a)

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))  
    B = [0] * N

    for j in range(min(K, 41)):
        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
        B = [0] * N

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

if __name__ == '__main__':
    main()

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
a=A[:]
for _ in range(K):
    t=[0]*(N+1)
    for i in range(N):
        ti=a[i]
        t[max(0,i-ti)]+=1
        t[min(N,i+ti+1)]-=1
    for i in range(N):
        t[i+1]+=t[i]
    a=t[:N]
    if min(a)==N:
        break
print(*a)

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

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

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


n, k = map(int, input().split())
A = np.array([*map(int, input().split())],dtype=np.int64)



@jit
def loop(A):
    for _ in range(k):
        b=np.zeros(n,dtype=np.int64)
        
        for i,v in enumerate(A):
            
            b[max(0,i-v)]+=1
                
            
                
            
            if i+v+1<n:
                b[i+v+1]-=1
            
            
        
        
        
        
        
        A=np.cumsum(b)
        
        if min(A)==n:
            break
    return A
print(" ".join(map(str,loop(A))))

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
foo = [[0 for k in range(N)] for k in range(42)]
for k in range(len(A)):
    foo[0][k] = A[k]
if K <42:
    for q in range(K):
        unko = [0 for k in range(N)]
        for k in range(N):
            if k + foo[q][k]+1 < N:
                unko[k + foo[q][k]+1] -=1
            unko[max(k - foo[q][k], 0)] +=1
        unchi = 0
        for k in range(N):
            unchi += unko[k]
            foo[q+1][k] = unchi
        
        
        count =0
        for l in range(N):
            if foo[q+1][l] < N:
                break
            else:
                count +=1
        
        if count == N:
            break
        
                        
        
    print(" ".join(map(str, foo[q+1])))

     
else:
    print((str(N)+" ")*(N-1)+str(N))

Solution (Python):
from numba import jit
@jit
def main():
    n,k = map(int,input().split())
    lamps = list(map(int,input().split()))
    for ki in range(k):
        lamplog = [0]*(n+1)
        for i in range(n):
            lamplog[max(0,i-lamps[i])  ] += 1   
            lamplog[min(i+lamps[i]+1,n)] -= 1   
        
        for i in range(n):                      
            lamplog[i+1] += lamplog[i]
        
        lamplog.pop()
        if(lamplog == lamps):                   
            break
        lamps = lamplog                         
    return lamplog

lamplog = main()
ans = ""
for i in range(len(lamplog)):
    ans += str(lamplog[i]) +" "
print(ans.rstrip())

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

for _ in range(K):
    B = [0] * N
    for i, d in enumerate(A):
        l = max(0, i-d)
        r = min(N-1, i+d)
        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 min(A) == N:
        break

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

Solution (Python):
n,k=map(int,input().split())
arr=list(map(int,input().split()))
for i in range(k):
    b=[0]*(n)
    c=0
    for j in range(n):
        if j-arr[j]>=0:
            b[j-arr[j]]+=1
        else:
            b[0]+=1
        if j+arr[j]+1<n:
            b[j+arr[j]+1]-=1
    for i in range(1,n):
        b[i]=b[i]+b[i-1]
    for i in range(n):
        if b[i]==n:
            c+=1
    if c==n:
        break
    arr=b.copy()
print(*b)

Solution (Python):
import math
N,K = map(int,input().split())
A = list(map(int,input().split()))
for j in range(min(K,50)):
	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 < N-1:
			B[r+1] -= 1
	for i in range(1,N):
		B[i] += B[i-1]
	A = B
print(' '.join(map(str,A)))

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

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            
            
            if j<n:
                b[j]-=1
        
        
        
        
        
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

if '__main__' == __name__:
    main()

Solution (Python):
import copy

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]
        l = max(0, j - d)
        r = min(j + d + 1, n)
        b[l] += 1
        b[r] -= 1

    for j in range(n):
        b[j + 1] += b[j]
    b = b[:-1]

    if b == a:
        break
    a = copy.deepcopy(b)
print(*a, sep=' ')

Solution (Python):
import numpy as np
from numba import jit
N,K=map(int,input().split())
A=np.array(list(map(int,input().split())),dtype=np.int64)
@jit
def loop(a,k):
  if k>41:
    ans=np.ones(N,dtype=np.int64)*N
  else:
    ans=a
    for j in range(k):
      B=np.zeros(N+1,dtype=np.int64)
      for i in range(N):
        B[max(0,i-int(ans[i]))] +=1
        B[min(N,i+int(ans[i])+1)] -=1
      ans=np.cumsum(B)[:N]
  return ans

for i in loop(A,K):
  print(i)

Solution (Python):
from itertools import accumulate
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

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

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):
        imos[max(0, i-A[i])] += 1
        imos[min(N-1, i+A[i])+1] -= 1
    
    for i in range(1, N+1):
        imos[i] += imos[i-1]
        
    for i in range(N):
        A[i] = imos[i]
    
    if A==[N]*N:
        print(*A)
        exit()

print(*A)

Solution (Python):
import numpy as np 
from numba import njit
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=np.array(a,np.int64)

@njit(cache=True)
def imo(a):
    imos=np.zeros(n+1,np.int64)
    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,i+a[i]+1)]-=1
    
    immo=np.zeros(n+1,np.int64)
    immo=np.cumsum(imos)
    return immo[:n]


for _ in range(min(k,41)):
    a=imo(a)
    
print(*a)

Solution (Python):
import copy
from functools import lru_cache



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

    
    
    

    def func(A):
        B = [0] * N
        for i in range(N):
            l = max(0, i - A[i])
            r = min(i + A[i], N-1)
            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 k in range(K):
        
        A = func(A)
        if k >= 50:
            break

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

if __name__ == "__main__":
    resolve()

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

Solution (Python):

N, K = list(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
    for i in range(1,N):
        B[i] += B[i-1]
    B,A = A,B
    if min(A) == N:
        break
print(*A)

Solution (Python):
import numpy as np

from numba import njit
@njit(cache=True)
def solve(N,K,A):
    for _ in range(K):
        B = np.zeros(N,dtype=np.int64)
        for i in range(N):
            l = max(0,i-A[i])
            r = min(N-1,i+A[i])
            B[l] += 1
            if N > r+1:
                B[r+1] -= 1
        
        A = np.cumsum(B)
        if np.all(A==N):
            break

    return A

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

    A = solve(N,K,A)
    print(*A)

main()

Solution (Python):

N, K = list(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
    for i in range(1,N):
        B[i] += B[i-1]
    A,B = B,A
    if min(A) == N:
        break
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())))


@njit
def search(a):
  B = np.zeros_like(a)
  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 = np.cumsum(B)
  return B

for _ in range(K):
  A = search(A)
  if min(A) == N:
      break
A = map(str, A)
print(' '.join(A))

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

cnt=0
while cnt<K:
  blist=[0]*(N+1)
  for i in range(N):
    l=max(0,i-alist[i])
    r=min(N-1,i+alist[i])
    blist[l]+=1
    blist[r+1]-=1
  
  alist[0]=blist[0]
  for i in range(1,N):
    alist[i]=alist[i-1]+blist[i]
  cnt+=1
  
  
  if min(alist)==N:
    break
  

print(*alist)

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

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 = [imosu[0]]
  for i in imosu[1:N]:
    A.append(A[-1]+i)
  K -= 1
  if min(A) == N:
    break
  
print(*A)

Solution (Python):
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')
from itertools import accumulate


N, K = MI()
A = LMI()

for _ in range(min(50, K)):
    accum = [0] * (N + 1)
    for i, a in enumerate(A):
        l, r = max(0, i - a), min(N - 1, i + a)
        accum[l] += 1
        accum[r + 1] -= 1
    A = list(accumulate(accum))[:-1]
print(*A)

Solution (Python):
import numpy as np 
from numba import jit
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=np.array(a,np.int64)

@jit
def imo(a):
    imos=np.zeros(n+1,np.int64)
    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,i+a[i]+1)]-=1
    
    immo=np.zeros(n+1,np.int64)
    immo=np.cumsum(imos)
    return immo[:n]


for _ in range(min(k,41)):
    a=imo(a)
    
print(*a)

Solution (Python):
import numpy as np 
from numba import njit
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=np.array(a,np.int64)

@njit('(i8[::1],)', cache=True)
def imo(a):
    imos=np.zeros(n+1,np.int64)
    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,i+a[i]+1)]-=1
    
    immo=np.zeros(n+1,np.int64)
    immo=np.cumsum(imos)
    return immo[:n]


for _ in range(min(k,41)):
    a=imo(a)
    
print(*a)

Solution (Python):
import sys
N, K = map(int, input().split())
if K > 42:
    print(" ".join(map(str, [N] * N)))
    sys.exit()
A = [int(i) for i in input().split()]
DP = [[0 for _ in range(N)] for _ in range(K+1)]
for i in range(N):
    DP[0][i] = A[i]

for i in range(1, K+1,1):
    B = [0] * N
    for j in range(N):
        pl, mi = min(j + DP[i-1][j], N-1), max(j - DP[i-1][j], 0)
        B[mi] += 1
        if pl + 1 < N:
            B[pl + 1] -= 1
    for j in range(1, N):
        B[j] += B[j-1]
    DP[i] = B
print(" ".join(map(str, DP[K])))

Solution (Python):

import numpy as np
from numba import b1, i8, njit, types


@njit(types.Tuple((i8[:], b1))(i8[:]), cache=True)
def f(A):
    n = len(A)
    ret = np.zeros_like(A)
    for x, p in enumerate(A):
        ret[max(0, x-p)] += 1
        if x+p+1 < n:
            ret[x+p+1] -= 1
    ret = ret.cumsum()
    return ret, np.all(A == n)


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(tuple(map(int, args[1].split())), int)
    for _ in range(k):
        A, satulated = f(A)
        if satulated:
            break

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


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))