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 



Sample input:
5 1
1 0 0 1 0


Sample output:
1 2 2 1 2

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit


@njit
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import jit


@jit("i8[:](i8, i8, i8[:])", nopython=True, cache=True)
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import jit, i8


@jit(i8[:](i8, i8, i8[:]), nopython=True)
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import jit


@jit("i8[:](i8, i8, i8[:])", nopython=True)
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import jit


@jit("i8, i8, i8[:]", nopython=True)
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import jit


@jit
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit


@njit("i8, i8, i8[:]")
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import jit


@jit("i8, i8, i8[:]")
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    for _ in range(k if k < 60 else 60):
        imos = [0] * (n + 1)
        for i in range(n):
            left = max(0, i - A[i])
            imos[left] += 1
            right = min(n, i + A[i] + 1)
            imos[right] -= 1

        B = list(accumulate(imos))
        A = B
    print(*A[:n])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

for _ in range(K):
    flg = True
    imos = [0]*(N+1)
    for i in range(N):
        imos[max(0, i-A[i])] += 1
        imos[min(N, i+A[i]+1)] -= 1
    A = [0]*N
    c = 0
    for i in range(N):
        c += imos[i]
        A[i] = c
        if c != N:
            flg = False
    if flg is True:
        print(*([N]*N), sep=' ')
        exit()


print(*A)

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8[:](i8,i8,i8[:])", cache=True)
def solve(N, K, A):
    for _ in range(min(41, K)):
        A_cumsum = np.zeros(shape=N, dtype=np.int64)
        for i in range(N):
            A_cumsum[max(0, i - A[i])] += 1
            b = i + A[i] + 1
            if N - 1 < b:
                pass
            else:
                A_cumsum[b] -= 1
        A = np.cumsum(A_cumsum)
    return A


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

    ans = solve(N, K, A)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

import numpy as np
from numba import njit

N_ko, K_kai = map(int, input().split())
A_list = list(map(int, input().split()))
A = np.array(A_list, dtype=np.int64)

@njit
def cal_cumsum(A):
    Light_length = np.zeros(N_ko, dtype=np.int64)
    
    for i in range(N_ko):
        left = max(0, i - A[i])
        right = min(N_ko - 1, i + A[i])
        
        Light_length[left] += 1
        
        if (right + 1 < N_ko):
            Light_length[right + 1] -= 1
    
    Light_length = np.cumsum(Light_length)

    return(Light_length)

for k in range(min(42, K_kai)):
    A = cal_cumsum(A)


print(*A)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
c=0
while True:
    b=[0]*n
    if c==k:
        break
    for i in range(n):
        l=max(i-a[i],0)
        r=min(n-1,i+a[i])
        b[l]+=1
        if r+1<n:
            b[r+1]-=1
    f=True
    if b[0]!=n:
        f=False
    for i in range(1,n):
        b[i]+=b[i-1]
        if b[i]!=n:
            f=False
    a=b
    c+=1
    if f:
        break
print(*a)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(min(K, 50)):
    B = [0 for k in range(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()
   
for b in B:
    print(b, end=" ")

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)

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

    for _ 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+1 < N:
                B[r+1] -= 1
        for i in range(N-1):
            B[i+1] += B[i]
        A = B

    print(*B)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
*A, = map(int, input().split())

b = [i for i in A]
for c in range(K):
    buf = [0]*(N+1)
    for i, j in enumerate(b):
        buf[max(i-j, 0)] += 1
        buf[min(i+j+1, N)] -= 1
    for i in range(1, N+1):
        buf[i] += buf[i-1]
    b = [buf[i] for i in range(N)]
    if all([i==N for i in b]):
        break

print(*b)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

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

@njit
def imos(A):
    B = np.zeros(N, dtype=np.int64)
    for i,x in enumerate(A):
        a = max(0, i-x)
        b = min(i+x, N-1)
        B[a] += 1
        if b+1 <= N-1:
            B[b+1] -= 1
    B = np.cumsum(B)
    return B

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    acc = [0 for j in range(n+1)]
    for j in range(n):
        acc[max(0, j - a[j])] += 1
        acc[min(n-1, j + a[j]) + 1] -= 1
    for j in range(n):
        acc[j+1] += acc[j]
    a = acc[:-1]
    if sum(a) == n * n:

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_c

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

while K > 0:
    K -= 1
    # imos法 (B)
    B = [0] * (N + 1)
    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

    C = 0
    for j in range(N):
        C += B[j]
        A[j] = C

    if set(A) == set([N]):
        break

print(*A)

Submission status: Accepted

Solution code:
import itertools
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
for _ in range(K):
    cumsum = [0] * (N + 2)
    for i, a in enumerate(A):
        i += 1
        cumsum[max(0, i - a)] += 1
        cumsum[min(i + a + 1, N + 1)] -= 1
    A = list(itertools.accumulate(cumsum))[1:N + 1]
    if min(A) == N:
        break
print(' '.join(map(str, A)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, AS):
    for _i in range(K):
        d = [0] * (N + 1)
        for i in range(N):
            x = AS[i]
            d[max(i - x, 0)] += 1
            d[min(i + x + 1, N)] -= 1
        cur = 0
        ret = [0] * N
        for i in range(N):
            cur += d[i]
            ret[i] = cur
        AS = ret
        if all(x == N for x in ret):
            return ret

    return ret


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

    print(*solve(N, K, AS))


T1 = """
5 1
1 0 0 1 0
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    1 2 2 1 2
    """


T2 = """
5 2
1 0 0 1 0
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    3 3 4 4 3
    """


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
n, K = map(int, input().split())
a = list(map(int, input().split()))
s = [[0]*n for _ in range(100)]
s[0] = a

tmp = [0] * (n+1)
for i in range(K):
    if sum(s[i]) == n**2:
        print(*([n] * n))
        break
    for j in range(n):
        x = s[i][j]
        l, r = max(0, j-x), min(n, j+x+1)
        tmp[l] += 1
        tmp[r] -= 1
    
    for j in range(n):
        tmp[j+1] = tmp[j] + tmp[j+1]
        s[i+1][j] += tmp[j]
    tmp = [0] * (n+1)
else: print(*s[K])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
L = [0 for _ in range(N+1)]
cnt = 0
while min(A) < N and cnt < K:
    cnt += 1
    for i in range(N):
        L[max(i-A[i], 0)] += 1
        L[min(i+A[i]+1, N)] -= 1
    for i in range(N):
        L[i+1] += L[i]
        A[i] = L[i]
        L[i] = 0
for i in range(N):
    print(A[i], end = ' '*(i!=N-1))

Submission status: Accepted

Solution code:
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    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):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        B = list(accumulate(B))
        
        A=B[:-1]

        if A==[n]*(n):
            break
    
    

    print(*A)    
    
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    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):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B[:-1]

        if A==[n]*(n):
            break
    
    

    print(*A)    
    
resolve()

Submission status: Accepted

Solution code:
def aaa(n,k,a):
    for f in range(k):
        a1=[0]*(n+1)
        for x in range(n):
            y=max(0,x-a[x])
            a1[y]=a1[y]+1    
            z=min(n-1,x+a[x])
            a1[z+1]=a1[z+1]-1
        a[0]=a1[0]
        for x in range(1,n):    
            a[x]=a[x-1]+a1[x]
        if a==[n]*n:
            break
    return a

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]

b=aaa(n,k,a)
for i in range(n):
    print(b[i])

Submission status: Accepted

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

for i in range(min(50, k)):
    DP = [0] * (n+1)
    for j in range(n):
        light = A[j]
        DP[max(0, j-light)] += 1
        DP[min(n, j+light+1)] -= 1

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

    A = DP[:-1]

print(*A)

Submission status: Accepted

Solution code:
# 東京海上日動 プログラミングコンテスト2020 C
import numpy as np
from numba import njit
n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)

@njit
def imos(n, A):
    B = np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        left = max(0, i - A[i])
        right = min(n, i + A[i] + 1)
        B[left] += 1
        B[right] -= 1
    B = np.cumsum(B)
    return B[:-1]

def solve(n,k,A):
    for i in range(k):
        A = imos(n, A)
        min_A = min(A)
        if min_A == n:
            return A
    return A

ANS = solve(n, k, A)
print(' '.join(map(str, ANS)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    L = lmi()

    for _ in range(k):
        if min(L) == n:
            break
        imos = [0] * n
        for i in range(n):
            num = L[i]
            imos[max(0, i - num)] += 1
            if i + num + 1 <= n - 1:
                imos[i + num + 1] -= 1
        for i in range(1, n):
            imos[i] += imos[i-1]
        L = imos
    
    print(*L, sep=' ')



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
N,K = map(int,input().split())
A = np.array(input().split(),dtype=int)
I = np.arange(N)
for i in range(K):
  X = np.zeros(N+1,int)
  np.add.at(X,np.maximum(I-A,0),1)
  np.add.at(X,np.minimum(I+A+1,N),-1)
  A = X.cumsum()[:-1]
  if np.all(A==N):
    break
print(*A)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
 
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int64)
 
@njit
def imos(a):
  b = np.zeros(n+1, dtype=np.int64)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  b = np.cumsum(b)[:-1]
  return b
 
for q in range(k):
  a = imos(a)
  if np.min(a)==n:
    break
    
print(*a)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
 
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int64)
 
@njit
def loop1(a):
  b = np.zeros(n+1, dtype=np.int64)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  b = np.cumsum(b)[:-1]
  return b
 
for q in range(min(42, k)):
  a = loop1(a)
    
print(*a)

Submission status: Accepted

Solution code:
import os
import heapq
import sys
import math
import operator
from collections import defaultdict
from copy import copy
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inar():
    return [int(k) for k in input().split()]


def main():
    n,k=map(int,input().split())
    ar=list(map(int,input().split()))
    fr=[0]*(n+1)
    while(k):
        for i in range(n):
            mn=max(0,i-ar[i])
            mx=min(n-1,i+ar[i])
            fr[mn]+=1
            fr[mx+1]-=1
        k-=1
        for i in range(1,n):
            fr[i]=fr[i]+fr[i-1]
        ok=True
        for i in range(n):
            if(ar[i]!=fr[i]):
                ok=False
                break
        if(ok):
            break
        ar=copy(fr)
        fr = [0] * (n + 1)
    for i in range(n):
        print(ar[i],end=' ')
    print()












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


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
now = inpl()
now.append(0)
for _ in range(k):
    pre = now[::]
    now = [0] * (n+1)
    for j in range(n):
        a = max(0,j-pre[j])
        b = min(n,j+pre[j]+1)
        now[a] += 1
        now[b] -= 1
    x = 0
    mi = INF
    for j in range(n):
        x += now[j]
        mi = min(mi,x)
        now[j] = x
    if mi == n:
        break
print(*now[:n])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans1=[]
ans2=[]
ans1+=a
ans2+=a
for i in range(min(k,50)):
  now=0
  ans2=[]
  ans2+=ans1
  kans=[0]*n
  for j in range(n):
    if j+ans2[j]+1<=n-1:
      kans[j+ans2[j]+1]-=1
    now+=1+kans[j]
    #基本kans[j]は0だが終点は-1
    ans1[j]=now
  if ans1==list(range(1,n+1)):
    ans1=[n]*n
    break
  now=0
  kans=[0]*n
  for j in range(1,n+1):
    if n-j-ans2[n-j]>=0:
      kans[n-j-ans2[n-j]-1]-=1
    now+=1+kans[n-j]
    #基本kans[j]は0だが終点は-1
    ans1[n-j]+=now-1



print(*ans1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
lst = list(map(int, input().split()))

if n**(1/2) <= k:
    lst = [n for _ in range(n)]
    print(*lst)
else:
    for _ in range(k):
        ans = 0
        dp = [0] * (n + 1)
        for _ in range(n):  
            mx = max(0,_ - lst[_])
            mn = min(n, _ + lst[_] +1)
            dp[mx] += 1
            dp[mn] -= 1
        
        for _ in range(n):
            ans = ans + dp[_]
            lst[_] = ans

    print(*lst[:n])

Submission status: Accepted

Solution code:
n , k = map(int,input().split())
a = list(map(int,input().split()))
for j in range(k):
    b = [0 for i in range(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
    for i in range(n-1):
        b[i+1] += b[i]
    if a == b:
        print(*b)
        exit()
    a = b[:]
print(*b)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
for k in range(K):
    B = [0] * N
    for n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    #print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    #print(B)
    if sum(A) == N**2:
        break
    else:
        A = B[:]
print(*A)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())

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

def IMOS(a):
    imos = [0]*n
    for i, ai in enumerate(a):
        imos[max(i-ai, 0)] += 1
        if i+ai+1 < n:
            imos[i+ai+1] -= 1
    for i in range(1, n):
        imos[i] += imos[i-1]
    return imos

for _ in range(k):
    if sum(a) == n*n:
        break
    a = IMOS(a)

print(*a)

Submission status: Accepted

Solution code:
def main(n,k,a):
  for _ in range(k):
    b=[0]*(n+1)
    x=0
    for i,j in enumerate(a):
      b[max(0,i-j)]+=1
      b[min(n,i+j+1)]-=1
    for i in range(n):
      b[i+1]+=b[i]
      if b[i]==n:
        x+=1
    a=b
    if x==n:
      break
  return a
N,K,*A=map(int,open(0).read().split())
r=main(N,K,A)
print(*r[:-1])

Submission status: Accepted

Solution code:
def main(n,k,a):
  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
    for i in range(n):
      b[i+1]+=b[i]
    if a==b:break
    a=b
  print(*a[:-1])
N,K,*A=map(int,open(0).read().split())
main(N,K,A)