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 update(a):
  n = len(a)
  b = np.zeros_like(a)
  for i,x in enumerate(a):
    l = max(0, i-x)
    r = min(n-1, i+x)
    b[l] += 1
    if r+1 < n:
      b[r+1] -= 1
  b = np.cumsum(b)
  return b

n,k = map(int, input().split())
a = np.array(list(map(int, input().split())))

for _ in range(k):
  a = update(a)
  if np.all(a==n):
    break
    
print(' '.join(map(str, a)))

Submission status: Accepted

Solution code:
import sys
from numba import njit

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

@njit(cache=True)
def solve(n, k, a):
    if k == 0:
        return a
    b = [0]*n
    for _ in range(k):
        for i in range(n):
            if i > a[i]:
                b[i-a[i]] += 1
            else:
                b[0] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        for i in range(n-1):
            b[i+1] += b[i]
            a[i] = 0
        a[-1] = 0
        b, a = a, b
        if min(a) >= n:
            break
    return a

solve(0, 0, [0, 1, 2])
n, k = nm()
a = nl()
print(*solve(n, k, a))

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
from numba import njit

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

@njit
def solve(n, k, a):
    b = [0]*n
    for _ in range(k):
        for i in range(n):
            if i > a[i]:
                b[i-a[i]] += 1
            else:
                b[0] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        for i in range(n-1):
            b[i+1] += b[i]
            a[i] = 0
        a[-1] = 0
        b, a = a, b
        if min(a) >= n:
            break
    return a

n, k = nm()
a = nl()
print(*solve(n, k, a))

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

@njit
def update(a):
  n = len(a)
  b = np.zeros_like(a)
  for i,x in enumerate(a):
    l = max(0, i-x)
    r = min(n-1, i+x)
    b[l] += 1
    if r+1 < n:
      b[r+1] -=1
  b = np.cumsum(b)
  return b

n,k = map(int, input().split())
a = np.array(list(map(int, input().split())))

k = min(k, 100)

for _ in range(k):
  a = update(a)
print(' '.join(map(str,a)))

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
@njit
def op(A, n):
    B = np.zeros_like(A)
    for i, a in enumerate(A[:n]):
        B[max(i - a, 0)] += 1
        B[min(n - 1, a + i) + 1] -= 1
    return np.cumsum(B)

def main():
    n, k = list(map(int, input().split()))
    A = np.array(list(map(int, input().split())) + [0, ], dtype = np.int)
    for _ in range(k):
        A_new = op(A, n)
        if all(A[:n] == A_new[:n]):
            break
        A = A_new
    print(' '.join(list(map(str, A[:n]))))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

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

for i in range(n):
    print(a[i], end=' ')

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit
 
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit
def update(A):
  N = len(A)
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    l = max(0, i-x)
    r = min(N-1, i+x)
    B[l] += 1
    if r + 1 < N:
      B[r+1] -= 1
  B = np.cumsum(B)
  return B
    
    
N,K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
  A = update(A)
print(' '.join(A.astype(str)))

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit
 
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit('(i8[::1],)', cache=True)
def update(A):
  N = len(A)
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    l = max(0, i-x)
    r = min(N-1, i+x)
    B[l] += 1
    if r + 1 < N:
      B[r+1] -= 1
  B = np.cumsum(B)
  return B
    
    
N,K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
  A = update(A)
print(' '.join(A.astype(str)))

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B
 
N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
si = [0 for i in range(n+1)]
p = [1 for i in range(n)]
import copy 
for q in range(min(k,50)):
    v = 0
    s = copy.deepcopy(si)
    for i in range(n):
        if a[i] != 0:
            s[max(i-a[i],0)] += 1
            s[min(i+a[i]+1,n)] -= 1
            a[i] = 0
        else:
            a[i] = 1
    for i in range(n):
        v += s[i]
        a[i] += v
for i in range(n):
    print(a[i], end = ' ')

Submission status: Accepted

Solution code:
n,k,*l=map(int,open(0).read().split())
for _ in range(min(k,41)):
  s=[0]*-~n
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  for i in range(n): s[i+1]+=s[i]
  l=s
print(*l[:n])

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit, prange

#'''
N, K = map(int, input().split())
As = list(map(int, input().split()))
'''
N = 200000
K = 100000
As = [0] * N
#'''

@njit("i8[:](i8[:],)", cache = True)
def update(A_array):
    before_csum = np.zeros(N+1, np.int64)
    for i, A in enumerate(A_array[:N]):
        before_csum[max(0, i-A)] += 1
        before_csum[min(N, i+A+1)] -= 1
    return np.cumsum(before_csum)
    
A_array = np.array(As + [0], dtype = np.int64)
for k in range(min(K, 50)):
    A_array = update(A_array)
    
print(*A_array.tolist()[:N])

Submission status: Accepted

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

@jit
def imos(A):
    B=np.zeros_like(A)
    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:
import numpy as np
from numba import jit
@jit(cache = True)
def solve(n,k,A):
    l,r=0,0
    for i in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for x,y in enumerate(list(A)):
            l=max(0,x-y)
            r=min(n,x+y+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        if A[A==n].size==n:
            break
    return A
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=np.array(a)
X=solve(n,k,A)
print(*X,sep=' ')

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

#'''
N, K = map(int, input().split())
As = list(map(int, input().split()))
'''
N = 200000
K = 100000
As = [0] * N
#'''

@njit(cache = True)
def update(A_array):
    before_csum = np.zeros(N+1, np.int32)
    for i, A in enumerate(A_array[:N]):
        before_csum[max(0, i-A)] += 1
        before_csum[min(N, i+A+1)] -= 1
    return np.cumsum(before_csum)
    
A_array = np.array(As + [0], dtype = np.int32)
for k in range(min(K, 50)):
    A_array = update(A_array)
    
print(*A_array.tolist()[:N])

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('(i8[::1]),', cache=True)
def update(a):
    b = np.zeros_like(a)
    for i, x in enumerate(a):
        l = max(0, i - x)
        r = min(n - 1, i + x)
        b[l] += 1
        if r + 1 < n:
            b[r + 1] -= 1
    b = np.cumsum(b)
    return b
k = min(k, 100)
for i in range(k):
    a = update(a)
print(' '.join(a.astype(str)))

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

#'''
N, K = map(int, input().split())
As = list(map(int, input().split()))
'''
N = 200000
K = 100000
As = [0] * N
#'''

@njit()
def update(A_array):
    before_csum = np.zeros(N+1, np.int32)
    for i, A in enumerate(A_array[:N]):
        before_csum[max(0, i-A)] += 1
        before_csum[min(N, i+A+1)] -= 1
    return np.cumsum(before_csum)
    
A_array = np.array(As + [0], dtype = np.int32)
for k in range(min(K, 50)):
    A_array = update(A_array)
    
print(*A_array.tolist()[:N])

Submission status: Accepted

Solution code:
from itertools import accumulate

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

current_arr = A
if K > 41:
    print(*([N]*N))
    exit()
for _ in range(K):
    imos = [0] * N
    ruiseki = [0] * (N+1)
    for i, ai in enumerate(current_arr):
        imos[max([0, i-ai])] += 1
        if i+ai+1 < N:
            imos[i+ai+1] -= 1
    for j, im in enumerate(imos):
        ruiseki[j+1] = ruiseki[j] + im
    current_arr = ruiseki[1:]
#print(imos)
#print(ruiseki)
#print(*accumulate(imos))
print(*current_arr)

Submission status: Accepted

Solution code:
from itertools import accumulate
n,k = map(int, input().split())
As = list(map(int, input().split()))
for i in range(k):
    imos = [0] * (n+1)
    for i,a in enumerate(As):
        l = max(0, i-a)
        r = min(n, i+a+1)
        imos[l] += 1
        imos[r] -= 1
    acc = list(accumulate(imos))
    # 指数関数的に増える
    if acc[:-1] == As:
        print(*As)
        exit()
    As = acc[:-1]
print(*As)

Submission status: Accepted

Solution code:
import sys

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


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

    for x in range(k if k < 50 else 50):
        B = [0] * n
        for j in range(n):
            l = max(0, j - A[j])
            r = min(n - 1, j + A[j])
            B[l] += 1
            if r + 1 < n:
                B[r + 1] -= 1

        for x in range(1, n):
            B[x] += B[x - 1]
        A = B

    print(*A)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def action(A, N):
  B = [0] * N
  for i, bright in enumerate(A):
    s = max(0, i - bright)
    B[s] += 1
    e = min(N, i + bright)
    if e < N - 1:
      B[e + 1] -= 1
  
  for i in range(N - 1):
    B[i + 1] += B[i]
  return B

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

  for i in range(K):
    A = action(A, N)
    if (A[0] == N) & all(A):
      break
      
  print(*A, sep=" ")

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
for j in range(min(k, 42)):
    bit = [0 for _ in range(n)]
    for i in range(n):
        bit[max(i - a[i], 0)] += 1
        if i + a[i] + 1 < n:
            bit[i + a[i] + 1] -= 1
    result = [bit[0]]
    for i in range(n - 1):
        result.append(bit[i + 1] + result[-1])
    a = result
print(' '.join(list(map(str, a))))

Submission status: Accepted

Solution code:
n,k,*l=map(int,open(0).read().split())
for _ in range(k):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  s[0]=min(s[0],n)
  for i in range(1,n):
    s[i]=min(s[i-1]+s[i],n)
  s.pop()
  if s==l: break
  l=s
print(*l)

Submission status: Accepted

Solution code:
n,k,*l=map(int,open(0).read().split())
for _ in range(k):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  s[0]=min(s[0],n)
  for i in range(1,n):
    s[i]=min(s[i-1]+s[i],n)
  if s==l: break
  l=s
print(*l[:n])

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

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit


@njit
def solve(N, K, A):
    for _ in range(K):
        B = np.zeros(N + 1, dtype=np.int64)
        for i in range(N):
            a = A[i]
            B[max(0, i - a)] += 1
            B[min(N, i + a + 1)] -= 1
        A = np.cumsum(B)[:-1]
        if np.all(A == N):
            return A
    return A


N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
print(' '.join(map(str, solve(N, K, A))))

Submission status: Accepted

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

# imos法して，もう一回同じことを行う
# K回のシミューレション，途中で全てがKになったら打ち切る
for _ in range(K):
    new = [0] * N
    imos = [0] * N
    for i, a in enumerate(A):  # 0-indexにしても問題ない
        imos[max(0, i-a)] += 1
        if i+a+1 <= N-1:  # 右端まで照らすなら，終端は管理しない
            imos[i+a+1] -= 1
    for i in range(N):
        new[i] = new[i-1] + imos[i]
    # Aを上書き
    A = new
    if sum(A) == N*N:
        break
print(*A)

Submission status: Accepted

Solution code:
def draft(A, K, N):
    for _ in range(1, K+1):# 2 * 10**5
        tmp = [0]*(N+1)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        f = True
        for i in range(N):
            tmp[i+1] += tmp[i]
            A[i] = tmp[i]
            if A[i] != N:
                f = False
        if f:
            break
    for i in range(N):
        print(A[i], end=" ")

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k,*l=map(int,open(0).read().split())
for _ in range(min(k,41)):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  l[0]=min(s[0],n)
  for i in range(1,n):
    l[i]=min(l[i-1]+s[i],n)
print(*l)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

def solve(n,k,a):
    for _ in range(k):
        if a==[n]*n:    return a
        t = [0]*(n+1)
        for i,x in enumerate(a):
            t[max(0,i-x)] += 1
            t[min(n,i+x+1)] -=1
        a = list(accumulate(t))[:-1]
    return a

n,k = map(int,sys.stdin.readline().rstrip().split())
a = list(map(int,sys.stdin.readline().rstrip().split()))

print(*solve(n,k,a))

Submission status: Accepted

Solution code:
import copy
import sys
import math

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    B = [0] * n

    for i in range(min(k, 41)):
        for j in range(n):
            l = max(0, j-A[j]) #座標iの電球が照らす範囲の左端
            r = min(n-1, j+A[j]) #座標iの電球が照らす範囲の右端
            B[l] += 1
            if (r+1 < n):
                B[r+1] -= 1 # 後ほど累積和にしたときに、照らす範囲の右端より外には影響が及ばないようにあらかじめ1引いておく

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

        A = copy.deepcopy(B)
        B = [0] * n

    print(*A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from numba import jit
N, K = map(int, input().split())
A = list(map(int, input().split()))

@jit
def solve(k,n,a):
    for _ in range(k):
        Y = [0]*(n+1)
        for i, x in enumerate(a):
            Y[max(0, i-x)] += 1
            Y[min(n, i+x+1)] -= 1
        for j in range(1, n):
            Y[j] += Y[j-1]
        if a == Y[:-1]:
            break
        a = Y[:-1]
    return a

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

Submission status: Accepted

Solution code:
n,k,*l=map(int,open(0).read().split())
for _ in range(min(k,99)):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  l[0]=min(s[0],n)
  for i in range(1,n):
    l[i]=min(l[i-1]+s[i],n)
print(*l)

Submission status: Accepted

Solution code:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)

def main():
    N, K = LI()
    A = LI()

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

        if A == B:
            break
        A = B
    print(*A[:-1], sep=" ")


main()

Submission status: Accepted

Solution code:
import math
import numpy as np

n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]


for _ in range(k):
    new_a = np.zeros(n+1,dtype=int)
    np.add.at(new_a, np.maximum(0,np.arange(0, n)-a), 1)
    np.add.at(new_a, np.minimum(n,np.arange(0, n)+a+1), -1)
    a = new_a.cumsum()[:-1]
    if np.all(a==n):
        break

print(" ".join([str(x) for x in a]))

Submission status: Accepted

Solution code:
import math
N,K=map(int,input().split())
A=[0]*N
A=list(map(int,input().split()))

da=[0 for i in range(N)]
for k in range(K):
    B=[0 for i in range(N)]
    for i in range(N):
        l=max(0,i-A[i])
        r=min(N-1,i+A[i])
        B[l]=B[l]+1
        if(r+1<N):
            B[r+1]=B[r+1]-1
    for i in range(1,N):
        B[i]=min(N,B[i]+B[i-1])
    if(A==B):
        break
    A=B
b=[str(i) for i in B]
b=" ".join(b)
print(b)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = A + [0]

if K >= N - 1:
    ans = [N] * N
    print(*ans)

else:
    for i in range(K):
        tmp = [0] * (N + 1)
        
        for j in range(N):
            end_l = max(j - A[j], 0)
            end_r = min(j + A[j] + 1, N)
            
            tmp[end_l] += 1
            tmp[end_r] -= 1
        
        flg = tmp[0]
        
        for j in range(1, N):
            tmp[j] += tmp[j - 1]
            flg += tmp[0]
            A[j] = tmp[j]
        
        A[0] = tmp[0]
        
        if flg == N**2:
            break
            
    print(*A[:N])

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, j + a[j] + 1)] -= 1
    for j in range(n - 1):
        l[j + 1] += l[j]
    a = l
    if a.count(n) == n:
        break
print(*a[:n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# C

'''
5 100
1 0 0 1 0
'''

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

for k in range(K):
    B = [0] * N
    for i in range(N):
        l = max(0, i-prev[i])
        r = min(N-1, i+prev[i])
        # print(i, l, r)
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
    for i in range(1, N):
        B[i] += B[i-1]
    if prev == B:
        break
    prev = B

for b in B:
    print(b, end=' ')
print()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
 
K = min(K, 41)
 
# imos
for _ in range(K):
    B = [0 for _ 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

print(*A)

Submission status: Accepted

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

K = min(K, 41)

# imos
for _ in range(K):
    B = [0 for _ 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

for i in range(N):
    A[i] = str(A[i])
print(' '.join(A))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
C=[n for _ in range(n)]

for loop in range(k):
    B=[0 for _ in range(n)]
    for i in range(n):
        l,r=max(0,i-A[i]),i+A[i]+1
        B[l] +=1
        if r<n:B[r] -=1
    for i in range(n-1):
        B[i+1]=B[i]+B[i+1]
    A=B
    if A==C:break
print(*A)

Submission status: Accepted

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

@njit(i8[:](i8[:]),cache = True)
def calc(A):
    B = np.zeros_like(A)
    for i in range(len(A)):
        B[max(0,i - A[i])] += 1
        if i + A[i] + 1 < len(A):
            B[i + A[i] + 1] -= 1
    B = np.cumsum(B)
    return B

@njit(i8[:](i8,i8,i8[:]),cache = True)
def solve(N,K,A):
  for i in range(K):
    A = calc(A)
    if len(set(A)) == 1 and A[0] == N:
      break
  return A
  
import sys
readline=sys.stdin.readline
  
N,K = map(int,readline().split())
A = np.array(list(map(int,readline().split())))

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

Submission status: Accepted

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

@njit(i8[:](i8[:]),cache = True)
def calc(A):
    B = np.zeros_like(A)
    for i in range(len(A)):
        B[max(0,i - A[i])] += 1
        if i + A[i] + 1 < len(A):
            B[i + A[i] + 1] -= 1
    B = np.cumsum(B)
    return B
  
import sys
readline=sys.stdin.readline
  
N,K = map(int,readline().split())
A = np.array(list(map(int,readline().split())))

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

Submission status: Accepted

Solution code:
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	#data = [2]
	data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	#ans = [x for x in data if x!=0]
	ans = data[:]
	return ans

def solve(n,k,a):
	for j in range(int(min(42,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[:]

	for i in range(len(b)):
		print(b[i],end=" ")

def main():
	n,k = readInts()
	a = readInts()
	solve(n,k,a)

if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
from numba import njit

@njit(cache=True)
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:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    for i in range(min(k, 50)):
        b = [0] * (n + 1)
        for j in range(n):
            l = max(0, j - a[j])
            r = min(n - 1, j + a[j])
            b[l] += 1
            b[r + 1] -= 1
        for m in range(n):
            b[m + 1] += b[m]
        a = b[:-1]
    print(*a)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = [int(i) for i in input().split()]
loop = min(41,K)
for _ in range(loop):
    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
    for n in range(1,N):
        B[n] += B[n-1]
    A = [b for b in B]
print(*A)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from numba import jit
import sys
input = sys.stdin.readline


@jit
def solve(n, k, A):
    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]:
            break
        A = B[:-1]
    return A


def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    ans = solve(n, k, A)
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from numba import jit
import sys
input = sys.stdin.readline


@jit
def solve(n, k, X):
    for _ in range(k):
        Y = [0]*(n+1)
        for i, x in enumerate(X):
            Y[max(0, i-x)] += 1
            Y[min(n, i+x+1)] -= 1
        for j in range(1, n):
            Y[j] += Y[j-1]
        if X == Y[:-1]:
            break
        X = Y[:-1]
    return X


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from numba import njit

@njit
def calc(A):
    B = [0] * len(A)
    for i in range(len(A)):
        B[max(0,i - A[i])] += 1
        if i + A[i] + 1 < len(A):
            B[i + A[i] + 1] -= 1
    for i in range(1,len(B)):
        B[i] = B[i - 1] + B[i]
    return B

@njit
def solve(N,K,A):
  
  for i in range(K):
    A = calc(A)
    if len(set(A)) == 1 and A[0] == N:
      break
  return A
  
import sys
readline=sys.stdin.readline
  
N,K = map(int,readline().split())
A = list(map(int,readline().split()))

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

Submission status: Accepted

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

def solve():
    imos=[0]*(n+1)
    for i in range(n):
        mnind=max(0,i - a[i])
        mxind=min(n,i+ a[i]+1)
        imos[mnind]+=1
        imos[mxind]-=1
    for i in range(len(imos)-1):
        imos[i+1]+=imos[i]
    return imos[:n]

if k>50:
    k=50
for i in range(k):
    a = solve()
print(*a,sep=" ")