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:
#coding; utf-8
import copy
N, k = map(int,input().split())
A = list(map(int,input().split()))
B = [0] * N
A = [0] + A
#B = copy.copy(A)
#k = 10
for j in range(k):
    #print(A)
    n_light = [0] * (N+1)
    for i in range(N):
        d = A[i+1]
        l = i+1-d
        r = i+1+d
        #print(l, r)
        n_light[max(l, 1)] += 1
        if r+1 <= N:# and l != r:
            n_light[r+1] -= 1
        #print(n_light)
    #print(n_light)
    for i in range(1,N):
        n_light[i+1] += n_light[i]
    n_str = [str(i) for i in n_light]
    if len(set(n_light[1:])) == 1 and j > 2:
        #print(n_light)
        break
    #n_str = [str(i) for i in n_light]
    A = n_light
    #print(n_light) 
print(' '.join(n_str[1:]))

Submission status: Accepted

Solution code:
#%%time
from itertools import accumulate
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 = [0]*(n+1)
  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
  #a = list(accumulate(b))
  #a = a[:-1]
   
  #if np.all(a == n):
   # break

for q in range(min(42, k)):
  a = loop1(a)
    
print(*a)

Submission status: Accepted

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

# imos法で区間和を計算する、をk回まで繰り返す
cnt = 0
while cnt < k:
    imos = [0] * (n + 1)
    for i in range(n):
        imos[max(i - a[i], 0)] += 1
        imos[min(i + a[i] + 1, n)] -= 1

    for i in range(n):
        imos[i + 1] += imos[i]

    a = imos[0:n]
    cnt += 1

    if min(a) == n:
        # a = [n, n, n, ..., n] になったら打ち切り
        break
print(*a)

Submission status: Accepted

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,K=nm()
A=nl()

imos_l=[0]*(N+1)

for i in range(K):    
    imos_l=[0]*(N+1)
    for j in range(len(A)): 
        imos_l[max(j-A[j],0)]+=1
        imos_l[min(j+A[j]+1,N)]-=1
    for j in range(len(imos_l)-1):
        imos_l[j+1]=imos_l[j]+imos_l[j+1]
    for j in range(len(A)):
        A[j]=imos_l[j]
    flag=True
    for j in range(len(A)):
        if(A[j]<N):
            flag=False
    if(flag):
        print(*A)
        sys.exit(0)

print(*A)

Submission status: Accepted

Solution code:
N,K,*A=map(int,open(0).read().split())
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])

Submission status: Accepted

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

for _ in range(k):
    new_A = [0]*(n+1)
    cnt = 0
    for i in range(n):
        a = A[i]
        if a == n:
            cnt += 1
        L = max(0, i-a)
        R = min(n, i+a+1)
        new_A[L] += 1
        new_A[R] -= 1
    A = list(accumulate(new_A))
    if cnt == n:
        break

print(*A[:-1])

Submission status: Accepted

Solution code:
N,K,*A=map(int,open(0).read().split())
for _ in range(K):
  B=[0]*(N+1)
  for i in range(N):
    B[max(0,i-A[i])]+=1
    B[min(N,i+A[i]+1)]-=1
  for i in range(N):B[i+1]+=B[i]
  if A==B:break
  A=B
print(*A[:-1])

Submission status: Accepted

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

Submission status: Accepted

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


for j in range(k):
    b=[0]*n
    for i in range(0,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,1):
        b[i]+=b[i-1]
    if a==b:
        break
    a=b

print(' '.join(map(str,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())))
@jit
def imos(a):
    tmp = np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        tmp[max(0, i - a[i])] += 1
        tmp[min(i + a[i] + 1, n)] -= 1
    tmp = np.cumsum(tmp)
    return tmp[:n]

for j in range(1, min(k+1, 50)):
    a = imos(a)
print(*a)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit, i8
input = lambda: sys.stdin.readline().rstrip()

@njit(i8[:](i8[:]), cache=True)
def count(a):
    tmp = np.zeros_like(a)
    for index, num in enumerate(a):
        left = max(0, index-num)      
        right = min(len(a)-1, index+num)  
        tmp[left] += 1              
        if right + 1 < len(a):
            tmp[right + 1] -= 1
    tmp = np.cumsum(tmp)
    return tmp

def main():
    n, k = map(int, input().split())
    a = np.array(list(map(int, input().split())))
    for _ in range(k):
        a = count(a)
        if len(set(a)) == 1 and n in set(a):
            print(*a)
            return
    print(*a)

if __name__ == '__main__':
    main()

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 numpy as np
from numba import njit

@njit #処理の並列化_これがない場合は'TLE'
def imos(n, a):
    l=np.zeros((n+1), dtype = np.int64)

    for i, x in enumerate(a):# x_光の強さ_これで照射範囲が決まる
        left = max(0, i - x) #StartIndex_照らせる範囲
        right = min(n, i + x + 1) #EndIndex + 1_照らせる範囲
        l[left] += 1 # 各々を'+1'と'-1'で表し...
        l[right] -= 1

    return np.cumsum(l)[:n] # 累積和をとる_cumulative sum

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

for _ in range(k):
    a = imos(n, a)
    if a.min() == n: # すべての要素が最大値'n'になるとbreak
        break

print(*a)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

@njit #処理の並列化_これがない場合は'TLE'
def imos(n, a):
    
    l=np.zeros((n+1), dtype = np.int64)

    for i in range(n):
        ai = a[i] # 光の強さ_これにより照らせる範囲が決まる
        start = max(0, i - ai) #StartIndex_照らせる範囲
        end = min(n, i + ai + 1) #EndIndex + 1_照らせる範囲
        l[start] += 1 # 各々を'+1'と'-1'で表し...
        l[end] -= 1
    return np.cumsum(l)[:n] # 累積和をとる_cumulative sum

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

for _ in range(k):
    a = imos(n, a)
    if a.min() == n: # すべての要素が最大値'n'になるとbreak
        break

print(*a)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

@njit #処理の並列化

def imos(n, a):
    
    l=np.zeros((n+1), dtype = np.int64)

    for i in range(n):
        ai = a[i] # 光の強さ_これにより照らせる範囲が決まる
        start = max(0, i - ai) #StartIndex_照らせる範囲
        end = min(n, i + ai + 1) #EndIndex + 1_照らせる範囲
        l[start] += 1 # 各々を'+1'と'-1'で表し...
        l[end] -= 1
    return np.cumsum(l)[:n] # 累積和をとる_cumulative sum

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

for _ in range(k):
    a = imos(n, a)
    if a.min() == n: # すべての要素が最大値'n'になるとbreak
        break

print(*a)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
List = list(map(int, input().split()))
 
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki
 
for i in range(K):
  List = imosu(List,N)
  if List.count(N) == N:
    break
print(*List)

Submission status: Accepted

Solution code:
import itertools

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

for i in range(K):
    TEMP = [0]*(N+1)
    for j in range(N):
        TEMP[max(0,j-A[j])] +=1
        TEMP[min(N,j+A[j]+1)] -=1
    A = list(itertools.accumulate(TEMP))
    if A[0] == N and A[N-1] == N:
        break

A.pop()
print(*A)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

@njit #処理の並列化
def imos(n,k,a):
    
    l=np.zeros((n+1),dtype=np.int64)
    for i in range(n):
        ai=a[i]
        start=max(0,i-ai) #StartIndex
        end=min(n,i+ai+1) #EndIndex + 1
        l[start]+=1
        l[end]-=1
    return np.cumsum(l)[:n]

if __name__=="__main__":
    n,k=map(int, input().split())
    a=list(map(int, input().split()))
    for _ in range(k):
        a=imos(n,k,a)
        if a.min()==n:
            break   
    
    print(*a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from itertools import accumulate

n,k = readints()
a = readints()

for _ in range(k):
    b = [0]*(n+1)
    for i in range(n):
        b[max(0,i-a[i])]+=1
        b[min(n,i+a[i]+1)]-=1
    a = list(accumulate(b))[:-1]
    if min(a)==n:
        break
printline(a)

Submission status: Accepted

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

for k in range(1,min(K+1,45)):
    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
print(*A)

Submission status: Accepted

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

for _ in range(min(k, 100)):
    new_a = [0]*n
    for i in range(n):
        d = a[i]
        new_a[max(i-d, 0)] += 1
        if i+d+1 <= n-1:
            new_a[i+d+1] -= 1
    for i in range(n-1):
        new_a[i+1] += new_a[i]

    a = new_a

print(*a)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
li = list(map(int,input().split()))
ans = [0]*(n+1)
tmp = [0]*(n+1)
tmp_sum = []
#print(ans)
#[0, 0, 0, 0, 0]
k = min(k,100)

for kkk in range(k):
    #print(li,'li')
    for i,l in enumerate(li):
        if l != 0:
            start = max(0,i-l)
            end = min(n,i+l+1)
            #print(start,'start',end,'end')
            tmp[start] += 1
            #print(end,len(tmp),'aaa')
            tmp[end] -= 1
    #print(tmp,'tmp')
    last = 0
    for t in tmp:
        last = t+last
        tmp_sum.append(last)
    for i,l in enumerate(li):
        if l == 0:
            tmp_sum[i] += 1
    ans = tmp_sum[:n]
    li = tmp_sum[:n]
    tmp = [0]*(n+1)
    tmp_sum = []
    #if len(set(ans)) == 1:
    #    break
print(*ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from itertools import accumulate
def main():
  n,k=map(int,input().split())
  a=list(map(int,input().split()))
  k=k if k<50 else 50
  for _ in range(k):
    b=[0]*(n+1)
    for i in range(n):
      ai=a[i]
      l,r=i-ai,i+ai+1
      l=0 if l<0 else l
      r=n if r>n else r
      b[l]+=1
      b[r]-=1
    b=tuple(accumulate(b))[:-1]
    a=b
    if min(set(b))==n:
      break
  print(*a)
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from sys import stdin
# from collections import defaultdict as dd
# from collections import deque as dq
# import itertools as it
# from math import sqrt, log, log2
# from fractions import Fraction

n, k = map(int, input().split())
intensity = list(map(int, stdin.readline().split()))

count = 0
while count < k:
    totsum = 0
    prefs = [0]*n
    zeros = []
    for i in range(n):
        l = i - intensity[i]
        r = i + intensity[i] + 1

        prefs[max(l, 0)] += 1
        if r <= n-1: 
            prefs[r] += -1
            
    for i in range(1, n):
        prefs[i] += prefs[i-1]
        totsum += prefs[i]
    
    if sum(prefs) == n*n:
        print(*prefs)
        exit()
    
    intensity = prefs
    count += 1

print(*prefs)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A=[*map(int,input().split())]
for i in range(k):
    B = [0]*n
    for j in range(n):
        d = A[j] # 強さ
        l = max(0, j-d) # 範囲
        r = j+d+1 # 範囲
        B[l] += 1
        if r <= n-1: B[r] -= 1
    is_same = True
    for j in range(n-1):
        B[j+1] = B[j+1] + B[j]
        if B[j+1] != n: is_same = False
    # print(B)
    if is_same: break
    A = B
# print(B)
print(*B,sep=' ')

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from itertools import accumulate

    n, k = map(int, readline().split())
    a = [*map(int, readline().split())]
    for _ in range(min(k, 41)):
        memo = [0] * n
        for i, aa in enumerate(a):
            if i > aa:
                memo[i - aa] += 1
            else:
                memo[0] += 1
            j = i - ~ aa
            if j < n:
                memo[j] -= 1
        a = [*accumulate(memo)]
    print(*a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    memo = [0] * (n + 1)
    for _ in range(k):
        flag = True
        for i, aa in enumerate(a):
            bf = (i - aa if i - aa >= 0 else 0)
            af = (i + aa + 1 if i + aa < n else n)
            memo[bf] += 1
            memo[af] -= 1
        for i in range(n):
            memo[i + 1] += memo[i]
            a[i] = memo[i]
            if a[i] != n:
                flag = False
            memo[i] = 0
        if flag:
            break
    print(*a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

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


fin = [N] * N

@njit(cache=True)
def calc_b(a):
    b = np.zeros(N, dtype=np.int64)
    for i, _a in enumerate(a):
        l = max(0, i - _a)
        r = min(N - 1, i + _a)

        # imos hou
        b[l] += 1
        if r + 1 < N:
            b[r + 1] -= 1

    b = np.cumsum(b)
    # print('b_sum', b)
    return b


for k in range(min(K,100)):
    # print('a', a)
    a = calc_b(a)
    # if all(a == fin):
    #     break

a = [str(_) for _ in a]
print(' '.join(a))
# print('step=', k)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
R = [N]*N
def update(A):
    b = [0]*N
 
    for i,a in enumerate(A):
        l = max(0,i-a)
        r = min(N-1,i+a)
 
        b[l] += 1
        if r+1 < N:
            b[r+1] -= 1
    
    res = []
    s = 0
    for i in b:
        s += i
        res.append(s)
    return res
 
for _ in range(K):
    A = update(A)
    if A == R:
      break
print(*A)

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        for j in range(n):
            memo[j + 1] += memo[j]
        a = memo[:-1]
        if a == [n] * n:
            break
    print(*a)


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):
    lis = [0]*(N+1)
    for j in range(N):
        lis[min(N,j+A[j]+1)] -= 1
        lis[max(0,j-A[j])] += 1
    cnt = 0
    for j in range(N):
        cnt += lis[j]
        A[j] = cnt
    cnt2 = 0
    for j in range(len(A)):
        if A[j] == N:
            cnt2 += 1
    if cnt2==N:
        break
print(' '.join(map(str,A)))

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

print(*A, sep=" ")

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
 
mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000
 
d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
 
N, K = LI()
A = LI()
 
if K > 50:
    print(" ".join([str(N) for i in range(N)]))
    sys.exit()
 
for i in range(K):
    A_new = [0 for i in range(N)]
    imos_table = [0 for i in range(N)]
 
    for j in range(N): # ここで一度状態の差分についてをimos_tableに保存
        left = max(0, j - A[j])
        right = j + A[j] + 1
        imos_table[left] += 1
        if right >= N:
            pass
        else:
            imos_table[right] -= 1
    
    # tmp を使って前から順に状態を計算していく
    tmp = 0
    for j in range(N):
        tmp += imos_table[j]
        A_new[j] += tmp
 
    A = copy.deepcopy(A_new)
 
print(" ".join(map(str, A)))

Submission status: Accepted

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

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

from itertools import accumulate

aa

for _ in range(k):
    d = [0] * n

    for i, a in enumerate(aa):
        d[max(i-a, 0)] += 1
        end = i+1+a
        if end < n:
            d[end] -= 1

    d = list(accumulate(d))
    if aa == d:
        break
    aa = d


print(' '.join(str(a) for a in aa))

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

    print(*A, sep=" ")



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

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

A_list = np.array([0]+list(map(int, input().split())))

@njit
def update(A_list):

  for j in range(min(K,46)):
    new_A=np.zeros(N+2,dtype=np.int64)
    for i in range(1,N+1):
      #print(new_A)
      mi=i-A_list[i]
      ma=i+A_list[i]
      if mi<0:
        mi=0
      if ma>N:
        ma=N
      #new_A[mi:ma+1]+=1
      new_A[mi]+=1
      new_A[ma+1]-=1

    A_list=np.cumsum(new_A)
    #if sum(A_list[1:N+1])==N*N:
    #  return(A_list)    
    #  break
      
  return(A_list)

A_list=update(A_list)
for i in range(1,N+1):
  print(A_list[i],end=" ")

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    for k in range(K):
        A_temp=[0]*(N+1)
        for i in range(N):
            A_temp[max(0,i-A[i])]+=1
            if i+A[i]+1<=N-1:
                A_temp[i+A[i]+1]-=1
            
        A[0]=A_temp[0]
        for j in range(1,N):
            A_temp[j]+=A_temp[j-1]
            A[j]=A_temp[j]
        for ai in A:
            if ai != N:
                break
        else:
            break
                
    print(' '.join([str(a) for a in A]))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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

for i in range(min(41, K)):
  B = [0] * N
  for n, A_n in enumerate(A):
    B_min = max(0, n-A_n)
    b_max = min(N-1, n+A_n)
    B[B_min] += 1
    if b_max+1 < N:
      B[b_max+1] -= 1
  
  sum = 0
  for n in range(len(A)):
    sum += B[n]
    A[n] = sum

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

Submission status: Accepted

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

def culc(L):
    subL=[0]*(n+1)

    for i in range(n):
        temp=L[i]
        bottom=max(i-temp,0)
        top=min(i+temp,n-1)

        subL[bottom]+=1
        subL[top+1]-=1
    
    resL=[0]*n
    resL[0]=subL[0]
    for i in range(1,n):
        resL[i]=resL[i-1]+subL[i]

    return resL

for i in range(min(k,41)):
    A=culc(A)

print(*A)

Submission status: Accepted

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

dp = [0] * (N + 1)
for k in range(K):
    sta = [max(i-A[i], 0) for i in range(N)]
    end = [min(i+A[i]+1, N) for i in range(N)]
    for s in sta:
        dp[s] += 1
    for e in end:
        dp[e] -= 1
    for i in range(1, len(dp)-1):
        dp[i] += dp[i-1]
    B = dp[:-1]
    if A == B:
        break
    A = B
    dp = [0] * (N + 1)
 
print(' '.join(map(str, A)))

Submission status: Accepted

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

def culc(L):
    subL=[0]*(n+1)

    for i in range(n):
        temp=L[i]
        bottom=max(i-temp,0)
        top=min(i+temp,n-1)

        subL[bottom]+=1
        subL[top+1]-=1
    
    resL=[0]*n
    resL[0]=subL[0]
    for i in range(1,n):
        resL[i]=resL[i-1]+subL[i]

    return resL

for i in range(min(k,50)):
    A=culc(A)

print(*A)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
imos = [0]*(n+1)
for j in range(k):
    if j==0:
        arr = A
    else:
        arr = imos
    imos = [0]*(n+1)
    for i,a in enumerate(arr):
        imos[max(i-a, 0)] += 1
        imos[min(i+a+1, n)] -= 1
    for k in range(1, len(imos)):
        imos[k] = imos[k]+imos[k-1]
    imos = imos[:-1]
    if set(imos)=={n}:
        break
print(*imos)

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
def main(N, K, A):
  for _ in range(min(K, 42)):
    A_ = np.zeros_like(A)
    for n in range(N):
      A_[max(0, n - A[n])] += 1
      if n + A[n] + 1  < N:
        A_[n + A[n] + 1] -= 1
    A = A_.cumsum()
        
  return A

print(*main(N, K, A))

Submission status: Accepted

Solution code:
import numpy as np
from numba import jit

@jit('i4[:](i4,i4,i4[:])',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 jit

@jit('i2[:](i2,i2,i2[:])',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 jit

@jit('i2[:](i2,i2,i2[:])')
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

import math

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

@njit
def solve(n,k,a):
    for i in range(k):
        new = np.zeros_like(a)
        for j in range(n):
            distance = j - a[j]
            if distance < 0:
                distance = 0
            last =  j + a[j]
            if last > n-1:
                last = n-1
            new[distance]+=1
            if last+1 < n:
                new[last+1]-=1
        a = np.cumsum(new)
        if np.all(a==n):
            break
    return a

a = solve(n,k,a)
print(" ".join(a.astype(str)))

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()
A = LI()

if K > 50:
    print(" ".join([str(N) for i in range(N)]))
    sys.exit()

for i in range(K):
    A_new = [0 for i in range(N)]
    imos_table = [0 for i in range(N)]

    for j in range(N):
        left = max(0, j - A[j])
        right = j + A[j] + 1
        imos_table[left] += 1
        if right >= N:
            pass
        else:
            imos_table[right] -= 1
    
    tmp = 0
    for j in range(N):
        tmp += imos_table[j]
        A_new[j] += tmp

    A = copy.deepcopy(A_new)

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

Submission status: Accepted

Solution code:
from itertools import accumulate


def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    for _ in range(operations):
        temp = [0] * (number + 1)
        for i, v in enumerate(dists):
            left = max(i - v, 0)
            right = min(i + v + 1, number)
            temp[left] += 1
            temp[right] -= 1
        templi = list(accumulate(temp))
        if templi == dists:
            break
        else:
            dists = templi
    dists.pop()
    print(*dists)


if __name__ == '__main__':
    main()

# Pypy 3 なら通る。Python 3 では無理。

Submission status: Accepted

Solution code:
from itertools import accumulate


def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    for ope_count in range(operations):
        temp = [0] * (number + 1)
        for i, v in enumerate(dists):
            left = max(i - v, 0)
            right = min(i + v + 1, number)
            temp[left] += 1
            temp[right] -= 1
        templi = list(accumulate(temp))
        if templi == dists:
            break
        else:
            dists = templi

    print(*list(dists)[:-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue


sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()

    for _ in range(k):
        imos = [0 for _ in range(n)]

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

        val = 0
        for i, im in enumerate(imos):
            val += im
            a[i] = min(val, n)

        if min(a) == n:
            break

    print(*a, sep=" ")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()

    for _ in range(min(k,42)):
        imos = [0 for _ in range(n)]

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

        val = 0
        for i, im in enumerate(imos):
            val += im
            a[i] = min(val, n)

        # if min(a) == n:
        #     break

    print(*a, sep=" ")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for l in range(k):
    if a==[n]*n: 
        break
    imos = [0]*(n+1)
    for i in range(n):
        imos[max(0,i-a[i]) ]+=1
        imos[min(n-1,i+a[i])+1 ]-=1

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

print(*a)