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 itertools import accumulate
from operator import add

N,K = map(int,input().split())
A = map(int,input().split()) 
for k in range(K):
    B = [0] * N
    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
    L = list(accumulate(B,add)) 
    #L = list(accumulate(B))[:]
    if L == A:
        break
    A = L
print(*A)

Submission status: Accepted

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

from itertools import accumulate
def resolve():
 
    N, K = map(int, inp().split())
    A = list(map(int, inp().split()))
 
    for _ in range(K):
        imos_table = [0]*(N+1)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = list(accumulate(imos_table))[:-1]
        if all([True if a == N else False for a in A]):
            print(*A)
            return
    else:
        print(*A)
        
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
# ----------------------------------------------------------- #

n, k = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
k = min(k, 50)
for _ in range(k):
    B = [0] * n
    for i in range(n):
        l = max(0, i-A[i])
        r = min(n-1, i+A[i])
        B[l] += 1
        if r+1 < n:
            B[r+1] -= 1
    for i in range(1, n):
        B[i] += B[i-1]
    A = deepcopy(B)

print(" ".join(str(b) for b in B))

Submission status: Accepted

Solution code:
from itertools import accumulate
#from operator import add

N,K = map(int,input().split())
A = map(int,input().split()) 
for k in range(K):
    B = [0] * N
    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
    #L = accumulate(B,add) 
    L = list(accumulate(B))[:]
    if L == A:
        break
    A = L
print(*A)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

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

@njit
def solve(N,K,A):
    for j in range(0, K):
        B = np.zeros(N, dtype=np.int64)

        for i in range(0,N):
            f = max(0, i - A[i])
            t = min(N-1, i + A[i])
            #for j in range(max(0, f), min(N, t)+1):
            #    B[j] += 1
            B[f] += 1
            if t+1 < N:
                B[t+1] -= 1
        A = np.cumsum(B)
        if np.all(A == N):
            return A
        i += 1
    return A
    

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

isMax = False
while K > 0 and not isMax:
    isMax = True
    B = [0] * N
    for i, d in enumerate(A):
        l = max(0, i - d)
        B[l] += 1
        r = i + d + 1
        if r < N:
            B[r] -= 1
    for i in range(N - 1):
        isMax &= (B[i] >= N)
        B[i + 1] += B[i]
    A = B
    K -= 1

print(*A[:N])

Submission status: Accepted

Solution code:

from itertools import accumulate
def resolve():

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

    for _ in range(K):
        imos_table = [0]*(N+1)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = list(accumulate(imos_table))[:-1]
        if all([True if a == N else False for a in A]):
            print(*A)
            return
    else:
        print(*A)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def a_to_b(A):
    c = [0] * N
    for i, a in enumerate(A):
        lb = max(0, i - a)
        c[lb] += 1
        ub = i + a + 1
        if ub < N:
            c[ub] -= 1
    tmp = 0
    B = []
    for ci in c:
        tmp += ci
        B.append(tmp)
    return B


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

ans = A
for _ in range(K):
    ans = a_to_b(ans)
    if sum(ans) == N ** 2:
        break

print(*ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

N, K = map(int, input().split())
*A, = map(int, input().split())
for i in range(K):
    a = [0]*N
    allN = True
    for j in range(N):
        l, r = max(j-A[j], 0), (j+A[j]+1)
        a[l] += 1
        if r < N:
            a[r] -= 1
        if A[j] != N:
            allN = False
    A = list(accumulate(a))
    if allN:
        break

print(*A)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np

def main():
    N, K = map(int, input().split())
    A = np.array(input().split(),dtype=int)
    I = np.arange(N)# 電球番号を保持
    for i in range(K):
        B = np.zeros(N+1, int)
        # ユニバーサル関数(ufunc)を利用して一度に処理
        np.add.at(B, np.maximum(0,I-A),1)
        np.add.at(B, np.minimum(N,I+A+1),-1)
        A = B.cumsum()[:-1]
        if np.all(A == N):
            break
    print(*A)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy
n,k = map(int,input().split())
ai = [int(i) for i in input().split()]

#old_ai = ai
cnt = 0

aij = [[0 for i in range(n)] for j in range(2)]
aij[0] = ai

while 1 == 1:
    li = [0]*(n+1)
    for i in range(n):
        li[max(0,i-aij[0][i])] += 1
        li[min(n,i+1+aij[0][i])] -= 1
        #print(li)
    #print(li)
    tmp = 0
    for i in range(n):
        if i == 0:
            aij[1][i] = li[i]
            tmp += aij[1][i]
        else:
            aij[1][i] = li[i] + aij[1][i-1]
            tmp += aij[1][i]
    #print(rui)
    if aij[1] == aij[0]:
        print(*aij[1])
        exit()
        break
    cnt += 1
    if cnt == k:
        print(*aij[1])
        exit()
    for i in range(n):
        aij[0][i] = aij[1][i]

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):
    c = [0]*n
    for i,j in enumerate(A):
        l = max(0,i-j)
        r = min(n-1,i+j)
        c[l] += 1
        if r+1 < n:
            c[r+1] -= 1
    #print(c)
    d = list(accumulate(c))
    if A == d:
        break
    A = d
print(" ".join(map(str,A)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    loop_count = min(K, 42)
    for _ in range(loop_count):
        light_range_list = [[0, 0] for _ in range(N)]
        for i, a in enumerate(A):
            start, end = max(0, i-a), min(N, i+a+1)
            light_range_list[i][0] = start
            light_range_list[i][1] = end
        ans = [0] * N
        for light_range in light_range_list:
            start, end = light_range[0], light_range[1]
            ans[start] += 1
            if end < N:ans[end] -= 1
        for i in range(N-1):
            ans[i+1] = ans[i] + ans[i+1]
        A = ans
    print(" ".join(list(map(str, ans))))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy
n,k = map(int,input().split())
ai = [int(i) for i in input().split()]

#old_ai = ai
cnt = 0
old_tmp = sum(ai)

while 1 == 1:
    #old_ai = copy.deepcopy(ai)
    li = [0]*(n+1)
    for i in range(n):
        li[max(0,i-ai[i])] += 1
        li[min(n,i+1+ai[i])] -= 1
        #print(li)
    #print(li)
    tmp = 0
    for i in range(n):
        if i == 0:
            ai[i] = li[i]
            tmp += ai[i]
        else:
            ai[i] = li[i] + ai[i-1]
            tmp += ai[i]
    #print(rui)
    if old_tmp == tmp:
        print(*ai)
        exit()
        break
    cnt += 1
    if cnt == k:
        print(*ai)
        exit()
    old_tmp = tmp

Submission status: Accepted

Solution code:
import copy
n,k = map(int,input().split())
ai = [int(i) for i in input().split()]

old_ai = ai
cnt = 0

while 1 == 1:
    old_ai = copy.deepcopy(ai)
    li = [0]*(n+1)
    for i in range(n):
        li[max(0,i-ai[i])] += 1
        li[min(n,i+1+ai[i])] -= 1
        #print(li)
    #print(li)
    tmp = 0
    for i in range(n):
        if i == 0:
            ai[i] = li[i]
            tmp += ai[i]
        else:
            ai[i] = li[i] + ai[i-1]
            tmp += ai[i]
    #print(rui)
    if ai == old_ai:
        print(*ai)
        exit()
        break
    cnt += 1
    if cnt == k:
        print(*ai)
        exit()
    old_ai = ai

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate
import math

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mina = min(A)
    for i in range(K):
        B = [0]*N
        for j in range(N):
            if j-A[j] >= 0:
                B[j-A[j]] += 1
            else:
                B[0] += 1
            if j+A[j]+1 < N:
                B[j+A[j]+1] -= 1
        A = list(accumulate(B[:]))
        mina = mina*2+1
        if mina >= N and A[0] == A[-1] == N:
            break
    print(*A)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)  # 電球iの光の強さAi
I = np.arange(N)  # 電球i
for i in range(K):
  X = np.zeros(N + 1, int)  # N = 5のとき、[0, 0, 0, 0, 0, 0]
  # いもす法
  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):
    # O(log N) 回操作を繰り返すと数列は収束しすべて N になる
    break
print(*A)  # intの配列をアンパックして出力

Submission status: Accepted

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


for i in range(K):
    #imos法(メモ)
    table = [0 for _ in range(N+1)]
    #数値がN個なのでN個の0の要素を作る
    #index0は空白、index1からx軸のランプがある位置に対応
    #1-Nまでのランプが格納されている
    for j in range(1,N+1):
        ai = As[j-1]
        #電球jが照らす左端をメモ
        #電球jが照らす左端はj-aiなので、ここに１を足す
        table[max(j-ai, 1)] += 1
        #電球jが照らす右端をメモ
        #電球jが照らす右端はj+aiなので、この次の項に-1を加える
        if j+ai<N:
            table[min(j+ai+1, N)] -= 1 

    #imos法(総和を求める)
    for j in range(1,N+1):
        table[j] += table[j-1]
        
    #答えになおす
    for j in range(N):
        As[j] = table[j+1]
        
    
    exit_condition = True
    for j in range(N):
        if As[j] != N:
            exit_condition = False
            break
        #要素が全てNの時に、conditionはtrueのまま
    
    if exit_condition:
        print(*As)
        exit(0)#条件が正常に動作した時、ここで終了とさせる
            

print(*As)

Submission status: Accepted

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

for i in range(k):
    table = [0 for _ in range(n*2)]
    # imos法
    for j in range(n):
        ai = a[j]
        # 電球が照らす左端
        table[max((j-ai)*2-1,0)] += 1
        # 電球が照らす右端
        table[min((j+ai)*2+1,n*2-1)] -= 1
    # 累積和
    for j in range(n*2):
        if j > 0:
            table[j] += table[j-1]
    for j in range(n):
        a[j] = table[j*2]
    flag = True
    for j in range(n):
        if a[j] != n:
            flag = False
            break
    if flag:
        print(*a)
        exit()
print(*a)

Submission status: Accepted

Solution code:
# C
import copy
import itertools

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

for j in range(k):
    b_list = [0]*n
#     print("a:",*a_list)
    for i in range(n):
        l = max(0, i-a_list[i])
        r = min(n-1, i+a_list[i])
        b_list[l] += 1
        if r+1 < n:
            b_list[r+1] -= 1
#     print("b:",*b_list)
    cumsum = list(itertools.accumulate(b_list))
    if cumsum == [n]*n:
        break
    a_list = cumsum
print(*cumsum)

Submission status: Accepted

Solution code:
import copy
n,k = map(int,input().split())
ai = [int(i) for i in input().split()]

old_ai = ai
cnt = 0

while 1 == 1:
    old_ai = copy.deepcopy(ai)
    li = [0]*(n+1)
    for i in range(n):
        li[max(0,i-ai[i])] += 1
        li[min(n,i+1+ai[i])] -= 1
        #print(li)
    #print(li)
    rui = [0]*n
    tmp = 0
    for i in range(n):
        if i == 0:
            ai[i] = li[i]
            tmp += ai[i]
        else:
            ai[i] = li[i] + ai[i-1]
            tmp += ai[i]
    #print(rui)
    if ai == old_ai:
        print(*ai)
        exit()
        break
    cnt += 1
    if cnt == k:
        print(*ai)
        exit()
    old_ai = ai

Submission status: Accepted

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

ML = 50
r = min(ML,k)

for l in range(r):
    imos = [0]*(n+1)
    for i in range(n):
        left = max(0,i-a[i])
        right = min(n,i+a[i]+1)
        
        imos[left] += 1
        imos[right] -= 1
        
    c = 0
    for i in range(n):
        c += imos[i]
        a[i] = c
        
print(*a)

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
import copy
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n,k=MI()
lis=LI()
for i in range(min(k,100)):
    lis2=[0 for i in range(n)]
    for i in range(n):
        lis2[max(0,i-lis[i])]+=1
        if i+lis[i]+1<n:
            lis2[i+lis[i]+1]+=-1
    lis=list(accumulate(lis2))
    #print(lis)
print(*lis)

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 ki in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for i,j in enumerate(A):
            l=max(0,i-j)
            r=min(n,i+j+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)

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:
from itertools import accumulate

N, K = map(int, input().split())
al = list(map(int, input().split()))
syusoku = [N] * N

for _ in range(K):
    s = [0] * N
    for i in range(N):
        left = i - al[i]
        right = i + al[i]
        if left < 0:
            left = 0
        s[left] += 1
        if right + 1 <= N - 1:
            s[right + 1] -= 1
        # print(left,right)
    al = list(accumulate(s))
    # print(al)
    if al == syusoku:
        print(*al)
        #print('end')
        exit()

print(*al)

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

N, K = map(int, input().split())
al = list(map(int, input().split()))
syusoku = [N] * N

for _ in range(K):
    s = [0] * N
    for i in range(N):
        left = i - al[i]
        right = i + al[i]
        if left < 0:
            left = 0
        s[left] += 1
        if right + 1 <= N - 1:
            s[right + 1] -= 1
        # print(left,right)
    al = list(accumulate(s))
    # print(al)
    if al == syusoku:
        print(*al)
        #print('end')
        exit()

print(*al)

Submission status: Accepted

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

    for i in range(K):

        arr = [0] * (N + 1)

        for ind,j in enumerate(A):
            arr[max(ind-j,0)] += 1
            arr[min(ind+j+1, N)] -= 1

        A[0] = arr[0]
        for k in range(N-1):
            A[k+1] = A[k] + arr[k+1]

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


if __name__ == "__main__":
    ans = solve()
    print(*ans)

Submission status: Accepted

Solution code:
def solve(N,K,A):
    for i in range(K):
        arr = [0] * (N + 1)

        for ind,j in enumerate(A):
            arr[max(ind-j,0)] += 1
            arr[min(ind+j+1, N)] -= 1

        A[0] = arr[0]
        for k in range(N-1):
            A[k+1] = A[k] + arr[k+1]

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


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

Submission status: Accepted

Solution code:
def update(A,N):
    B=[0 for i in range(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
    x = A[0] == B[0]
    A[0]=B[0]
    for i in range(1,N):
        B[i]+=B[i-1]
        x = x and A[i] == B[i]
        A[i]=B[i]
    return x

def resolve():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    for i in range(M):
        x=update(A,N)
        if x:
            break
    print(" ".join(map(str,A)))
resolve()

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, k = i_map()
    num_list = i_list()

    for _ in range(k):
        if num_list.count(n) == n:
            break
        tmp_list = [0] * (n+1)
        for j in range(n):
            l = max(0, j - num_list[j])
            r = min(j + num_list[j]+ 1, n)
            tmp_list[l] += 1
            tmp_list[r] -= 1
        for j in range(n):
            tmp_list[j+1] += tmp_list[j]
        num_list = deepcopy(tmp_list)
        
    print(*num_list[:n])

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):
    imo = [0] * (n + 1)
    for j in range(n):
        tmp = j-A[j]
        if tmp < 0:
            tmp = 0
        imo[tmp] += 1
        tmp2 = j+A[j]+1
        if tmp2 > n:
            tmp2 = n
        imo[tmp2] -=1
    if imo[0] == n and imo[n] == -n:
        A = [n] * n
        A = map(str, A)
        print(' '.join(A))
        exit()
    else:
        temp = 0
        for k in range(n):
            temp += imo[k]
            A[k] = temp
A = map(str, A)
print(' '.join(A))

Submission status: Accepted

Solution code:
import sys

from numba import njit

import numpy as np

readline = sys.stdin.buffer.readline


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

        for j, a in enumerate(A):
            l = max(0, j - a)
            r = min(j + a + 1, N)
            C[l] += 1
            C[r] -= 1

        A = np.cumsum(C)

    return A


def solver():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    A = f(N, K, np.array(A))
    print(*A[:-1])


solver()

Submission status: Accepted

Solution code:
# ac
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)       # aと同じ形状の配列を生成(https://deepage.net/features/numpy-zeros.html)
    for i, x in enumerate(a):  # enumerateはindex, valueを返す
        l = max(0, i - x)      # lampの照らす範囲の下限（左側）
        r = min(n - 1, i + x)  # lampの上限（右側）
        b[l] += 1              # 以下imos法
        if r + 1 < n:          # r+1はx=nの時（最後のサイクル）r+1=nでindexの指定に失敗するから弾く（indexは0~n-1）
            b[r + 1] -= 1
    b = np.cumsum(b)           # bの要素の累積和（フィボナッチ数列みたいな）（imos法の締め）
    return b


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

k = min(k, 41)                 # 今回の制限範囲のnなら41回も試行すればaの値が全て上限に達するのでそれ以上の試行は不要（解説PDF）
for _ in range(k):
    a = update(a)
print(' '.join(map(str, a)))   # joinメソッドはstrを''で区切って連結する

Submission status: Accepted

Solution code:
#素のPythonでは通りませんでしたが，PyPyを使ったら通りました
N, K = map(int, input().split())
As = list(map(int, input().split()))

for i in range(K):
    table = [0 for _ in range(N*2)]
    # imos法 - メモ
    for j in range(N):
        ai = As[j]
        # 電球が照らす左端をメモ
        table[max((j-ai)*2-1, 0)] += 1
        # 電球が照らす右端をメモ
        table[min((j+ai)*2+1, N*2-1)] -= 1
    
    # imos法 - シミュレート
    for j in range(N*2):
        if j > 0:
            table[j] += table[j-1]
    
    # 答えになおす
    for j in range(N):
        As[j] = table[j*2]
    
    exit_condition = True
    for j in range(N):
        if As[j] != N:
            exit_condition = False
            break
    
    if exit_condition:
        print(*As)
        exit(0)
            

print(*As)

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

[print(i, end=' ') for i in B]
print()

Submission status: Accepted

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

for _ in range(min(50, k)):
    l = [0]*(n+1)
    for i in range(n):
        l[max(i-a[i], 0)] += 1 #光の届く距離（後ろ）
        l[min(i+a[i]+1, n)] -= 1 #光が届かなくなる距離(前)
    add = 0
    for i in range(n):
        add += l[i] #光の届いている電球の数を累積
        a[i] = add
print(*a)

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

@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,input().split())
A=np.array(input().split(),np.int64)
K=min(K,100)
for _ in range(K):
    A=update(A)
print(" ".join(A.astype(str)))

Submission status: Accepted

Solution code:
# imos法
# 長さNの1次元配列において、「ある連続する区間に、ある数vを足す」という操作をK回繰り返した結果を高速で求める
# 電球の届く範囲をMax,Minで求めた
# 累積和  from itertools import accumulate
    
# 初期入力
    
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))       
l =0
r =N
#操作数が電球の数より多いとき
if N <=K:
    A=[N]*N
# imos法
else:
    for j in range(K):
        B =[0]*(N+1)
        for i in range(N):
            index =A[i]
            l =max(i -index,0)
            r =min(i +index +1,N) 
            B[l] +=1 
            B[r] -=1
        #累積和(imos法) 
        from itertools import accumulate
        del B[-1]
        A =list(accumulate(B))
        if sum(A) ==N*N:
            print(*A)
            sys.exit(0)
    
print(*A)

Submission status: Accepted

Solution code:
import numpy as np


def solve(N, K, A):
    E = np.arange(0, N)
    for _ in range(K):
        B = np.zeros(N + 1, dtype=np.int64)
        np.add.at(B, np.maximum(0, E - A), 1)
        np.add.at(B, np.minimum(E + A + 1, N), -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:
import numpy as np
from numba import njit


@njit('i8[:](i8,i8,i8[:])')
def solve(N, K, A):
    E = np.arange(0, N)
    for _ in range(K):
        B = np.zeros(N + 1, dtype=np.int64)
        for i_l, i_r in zip(np.maximum(0, E - A), np.minimum(E + A + 1, N)):
            B[i_l] += 1
            B[i_r] -= 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:
import math
n,k=map(int,input().split())
  
a=[0]*n
ans=[0]*n
a=list(map(int,input().split()))
check=math.ceil(math.log2(n))+1
if (k>=42):
  a=[n]*n
  print(" ".join(map(str,a)))
else:
  for _ in range(k):
    ans=[0]*n
    table=[0]*n
    for i in range(n):
      left=max(0,i-a[i])
      right=min(n-1,i+a[i])
      table[left]+=1
      if (right+1<n):
        table[right+1]-=1
      #print(left,right)
      #for j in range(left,right+1):
      #  ans[j]+=1
    #print(table)
    for i in range(1,n):
      table[i]+=table[i-1]
    a=table
 
  print(" ".join(map(str,a)))

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
import itertools

@njit
def imos(N,K,A):

    
    B=np.zeros((N+1),dtype=np.int64)
    #B=np.zeros((N+1))
    for i in range(N):
        a=A[i]
        start=max(0,i-a)
        end=min(N,i+a+1)
        B[start]+=1
        B[end]-=1
        #B=np.array(B)
    return np.cumsum(B)[: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:
# imos法
# 長さNの1次元配列において、「ある連続する区間に、ある数vを足す」という操作をK回繰り返した結果を高速で求める
# 
    
# 初期入力
    
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))
    
    
l =0
r =N
cumulative_sum =[0]*N
#操作数が電球の数より多いとき
if N <=K:
    A=[N]*N
# imos法
else:
    for j in range(K):
        B =[0]*(N+1)
        for i in range(N):
            index =A[i]
            if i-index <0:
                l=0
            else:
                l =i -index
            if i +index +1 >=N:
                r =N 
            else:
                r =i +index +1
            B[l] +=1 
            B[r] -=1
        #累積和(imos法) 
        from itertools import accumulate
        del B[-1]
        A =list(accumulate(B))
        if sum(A) ==N*N:
            print(*A)
            sys.exit(0)
    
print(*A)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit


@njit('i8[:](i8,i8,i8[:])')
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:
# 累積和で区間に操作ができる
import math
n,k=map(int,input().split())
A=list(map(int,input().split()))
kukan=[]
ans=[0]*n
for i in range(k):
    B=[0]*(n+1)#番兵は最後尾
    for j in range(n):
        l=max(0,j-A[j])
        r=min(j+A[j]+1,n)#右端の次の座標
        #print(l,r)
        B[l]+=1
        B[r]-=1
    for j in range(n):
        B[j+1]+=B[j]
    B.pop()#比較するために要素数を揃える
    if A==B:#飽和したら終わり
        break
    A=B#AにBをコピー
for b in B:
    print(b)

Submission status: Accepted

Solution code:
from itertools import accumulate

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


for _ in range(K):
    lamp = [0] * (N + 1)                    # imos法: 区間[l,r)　に要素を加算する操作を、lamp[l] += 1 と　lamp[r+1] -= 1　にすることで、
                                            # 情報の更新をO(1)で終わらせることができる。（愚直にやるとO(l-r) <= O(N)でアウト）
                                            # 右端を開にしているため、N+1 個の要素が必要。
    for i, a in enumerate(A):
        lamp[max(i-a,0)] += 1
        lamp[min(i+a+1,N)] -=1
    B = tuple(accumulate(lamp))[:-1]
    if B == A:
        break
    A = B


print(*A)

Submission status: Accepted

Solution code:
import copy
n,k,*A = map(int,open(0).read().split())
for _ in range(min(50,k)):
    B = [0] * (n+1)
    for i,d in enumerate(A):
        start = max(0,i-d)
        B[start] += 1
        end = min(n,i+d+1)
        B[end] -= 1
    light = 0 
    for i,b in enumerate(B[:n]):
        light += b
        A[i] = light

print(*A)

Submission status: Accepted

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

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

for x in range(K):
#	print(data)
	raise_data = [0] * (N + 1)
	for i, d in enumerate(data):
		raise_data[max(0, i - d)] += 1
		raise_data[min(N, i + d + 1)] -= 1
	
	height = 0
	ended = 0
	for i in range(N):
		height += raise_data[i]
		data[i] = height
		if height == N:
			ended += 1
	
	if ended == N:
#		print(x)
		break
	
print(*data)