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:
from numba import jit
import sys
input = sys.stdin.readline


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

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

    ans = ' '.join(list(map(str, A)))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(min(k, 45)):
    b = [0] * n
    for j in range(n):
        mi = max(0, j-a[j])
        ma = min(n-1, j+a[j])
        b[mi] += 1
        if ma + 1 <= n -1:
            b[ma+1] -= 1
    c = [0] * n
    s = 0
    for k in range(n):
        s += b[k]
        c[k] = s
    a = c

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import jit
 
readline = sys.stdin.readline
 
@jit
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)

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

@njit(cache=True)
def light(n,a_list):
    outcome= np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        outcome[max(0,i-a_list[i])] += 1
        outcome[min(n,i+a_list[i]+1)] -= 1
    outcome = np.cumsum(outcome)[:-1]
    return outcome

for _ in range(k):
    if min(a) == n:
        break
    a = light(n,a)

[print(aa,end=' ') for aa in a]

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit


def main(N, K, A):
    @njit(cache = True) # numpyの高速化．雲泥の差になった．知らなかった．
    def rep(N, A):
        B = np.zeros(N + 1, dtype=np.int64) # np.int64としないとnjitがエラー
        for x in range(N):
            minimum = max(0, x - A[x])
            maximum = min(N, x + A[x] + 1)
            # B[minimum:maximum] += 1   # これだと実質for文回してるような感じだから遅い？
            B[minimum] += 1
            B[maximum] -= 1
        # return B  # これだと実質for文回してるような感じだから遅い？
        return np.cumsum(B)[:-1]

    A = np.array(A, dtype=np.int64)
    for k in range(K):
        B = rep(N, A)
        if np.array_equal(A, B):
            break
        else:
            A = B
    return A



if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    print(' '.join([str(i) for i in main(N, K, A)]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import jit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K, *A = map(int, read().split())
 
@jit
def imos(A):
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    a = max(0,i-x)
    b = min(N-1,i+x)
    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:
import sys
import numpy as np
from numba import jit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K, *A = map(int, read().split())
K = min(50,K)

@jit
def imos(A):
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    a = max(0,i-x)
    b = min(N-1,i+x)
    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:

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

    print(*A)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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("i8[:](i8,i8[:])",cache=True)
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()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k):
  l=[0]*(n+1)
  for j in range(n):
    l[max(0,j-a[j])]+=1
    l[min(n-1,j+a[j])+1]-=1
  b=0
  for j in range(n):
    b+=l[j]
    a[j]=b
  if l[0]==n:
    break
print(*a,sep=' ')

Submission status: Accepted

Solution code:
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(cache=True)
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()

Submission status: Accepted

Solution code:
# 累積和
import numpy as np
from numba import njit

@njit(cache=True)
def loop(n, k, A):
    for _ in [0] * k:
        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
        A = np.cumsum(B)[:-1]
        #print(A)
        if np.all(A == n):
            return A
            break

    return A


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    A = np.array(a, dtype=np.int64)
    A = loop(n, k, A)
    print(*A)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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 range(min(k,41)):
        b=[0]*n
        for i,t in enumerate(a):
            if i>t:b[i-t]+=1
            else:b[0]+=1
            j=i-~t
            if j<n:b[j]-=1
        a=[*accumulate(b)]
    print(' '.join(map(str,a)))
main()

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
r=range(n)
for _ in a[:k][:41]:
 b=[0]*n*3
 for i in r:b[max(0,i-a[i])]+=1;b[i-~a[i]]-=1
 for i in r:b[i+1]+=b[i]
 a=b
print(*a[:n])

Submission status: Accepted

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


    for _ in range(K):
        counter=[0 for _ in range(N)]

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

        if counter==A:
            break
        else:
            A=counter

    for i in range(N):
        if i!=N-1:
            print(str(A[i])+" ",end="")
        else:
            print(A[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from numba import njit
@njit(cache=True)
def func(n, k, a):
    for i in range(k):
        b = []
        for i in range(n+1):
            b.append(0)
        for i in range(n):
            l = max(0, i - a[i])
            r = min(n, i + a[i] + 1)
            b[l] += 1
            b[r] -= 1
        for i in range(len(b)-1):
            b[i+1] += b[i]
        b = b[:n]
        if a == b:
            break
        else:
            a = b
    return b
if __name__ == '__main__':
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = func(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()))
p=0
while p<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
  p+=1
print(*a)

Submission status: Accepted

Solution code:
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)]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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=" ")

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""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")
    # first line is number of test cases
    N, K = map(int, stdin.readline().split())
    values = list(map(int, stdin.readline().split()))
    # values = []
    # for _ in range(N):
    #     values.append(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 #{}: {}".format(testcase + 1, result), file=stdout)
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result), file=stdout)


BUFSIZE = 8192


class FastIO(IOBase):
    # pylint: disable=super-init-not-called, expression-not-assigned
    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):
    # pylint: disable=super-init-not-called
    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
# for interactive call: do not add multiple times the handler
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())

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

    # 累計和はnumpyの方が高速
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# coding: utf-8
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())))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# coding: utf-8
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())))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
from numba import jit
import numpy as np


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

# for _ in range(min(k,int(math.log(n,2)))):

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

Submission status: Accepted

Solution code:
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
        #print(unko)
        #print(foo[q+1])
        count =0
        for l in range(N):
            if foo[q+1][l] < N:
                break
            else:
                count +=1
        
        if count == N:
            break
        
                        
        #print(foo)
    print(" ".join(map(str, foo[q+1])))

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

Submission status: Accepted

Solution code:
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   #末尾を出す
        # print(lamplog)
        for i in range(n):                      #累積和を計算
            lamplog[i+1] += lamplog[i]
        # print(lamplog)
        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())

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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 range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

if '__main__' == __name__:
    main()

Submission status: Accepted

Solution code:
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)