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 math
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = [int(_) for _ in input().split()]
for i in range(k):
    pre = [0] * (n + 1)
    for j in range(n):
        pre[max(0, j - a[j])] += 1
        pre[min(n, j + a[j] + 1)] -= 1
    total = 0
    good = True
    for j in range(n):
        total += pre[j]
        a[j] = total
        if a[j] != n:
            good = False
    if good:
        break
print(' '.join(map(str, a)))

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
ct=0
while min(A)<n and ct<k:
  B=[0]*n
  for i,a in enumerate(A):
    l,r=max(0,i-a),min(n,i+a+1)
    B[l]+=1    
    if r<n:
      B[r]-=1
  A[0]=B[0]
  for i in range(1,n):
    A[i]=A[i-1]+B[i]
  ct+=1
print(*A)

Submission status: Accepted

Solution code:
from itertools import accumulate

def solve(x,K):
    N = len(x)
    def transform(x):
        t = [0]*(N+1)
        for i,v in enumerate(x):
            t[max(i-v,0)] += 1
            t[min(i+v+1,N)] -= 1
        return tuple(v for v,_ in zip(accumulate(t),range(N)))

    for i in range(K):
        y = transform(x)
        if x == y:
            break
        x = y
    return x,i
from random import randrange
if __name__ == '__main__':
    N,K = map(int,input().split())
    x = tuple(map(int,input().split()))
    res, i = solve(x,K)
    print(*res)

    # for _ in range(10):
    #     x = tuple(randrange(2) for _ in range(10000))
    #     res,i = solve(x, 10000)
    #     print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n, k = LI()
    a = LI()
    for i in range(k):
        bit = [0] * (n+1)
        for j in range(n):
            bit[max(0, j - a[j])] += 1
            bit[min(n, j + a[j] + 1)] -= 1
        f = 0
        bit = list(itertools.accumulate(bit))
        for j in range(n):
            a[j] = bit[j]
            if a[j] < n:
                f = 1
        if f:
            continue
        break
    print(*a)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

N, K = map(int, input().split())
A = list(map(int, input().split()))
#A = [int(input()) for _ in range(N)]
#ABC = [list(map(int, input().split())) for _ in range(N)]

for k in range(K):
    lst = [0] * (N + 1)
    for i, a in enumerate(A):
        left = max(i - a, 0)
        right = min(N - 1, i + a)
        lst[left] += 1
        lst[right + 1] -= 1
    tmp = 0
    for i in range(N):
        tmp += lst[i]
        A[i] = tmp

    flag = 1
    for i in range(N):
        if A[i] != N:
            flag = 0
            break

    if flag:
        print(*([N] * N))
        exit()

print(*A)

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    for i in range(k):
        B=[0]*(n+1)
        for j in range(n):
            a=A[j]
            B[max(0,j-a)]+=1
            B[min(n,j+a+1)]-=1
        for j in range(n):
            B[j+1]+=B[j]
        A=B.copy()
        if sum(A[:-1])==n**2:
            break
    print(*A[:-1])
if __name__ == '__main__':
    main()

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()))
    for i in range(K):
        B = [0]*(N+1)
        for j in range(N):
            d = A[j]
            x = j-d
            y = j+d
            if x < 0:
                B[0] += 1
            else:
                B[x] += 1
            if N-1 < y:
                B[N] -= 1
            else:
                B[y+1] -= 1
        A = list( accumulate(B))
        check = True
        for j in range(N):
            if A[j] < N:
                check = False
        if check:
            break
    print(" ".join( map(str, A[:-1])))
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n,k=NM()
l=L()
dp=[]
from itertools import accumulate
for _ in range(min(100,k)):
    tl,l=l,[0]*(n+1)
    for i,j in enumerate(tl):
        l[max(0,i-j)]+=1
        l[min(n,i+j+1)]-=1
    l=list(accumulate(l))
print(" ".join(map(str,l[:n])))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
def move():
    global a
    s = [0] * (n + 1)
    for i in range(n):
        s[max(0, i - a[i])] += 1
        s[min(n, i + a[i] + 1)] -= 1
    for i in range(1, n + 1):
        s[i] += s[i - 1]
    if all(map(lambda i: a[i] == s[i], range(n))):
        return True
    a = s
    return False
for _ in range(k):
    if move():
        break
print(*a[:n])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(K):
  imos = [0] * (N + 1)
  for i in range(N):
    l = max(0, i - a[i])
    r = min(N - 1, i + a[i]) + 1
    imos[l] += 1
    imos[r] -= 1
  for i in range(N): imos[i + 1] += imos[i]
  a = imos[: -1]
  if a.count(N) == N: break
print(*a)

Submission status: Accepted

Solution code:
from collections import *
from math import *
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
b = [0 for i in range(n+1)]
cnt = 0
for i in range(k):
	b = [0 for i in range(n+1)]
	for i in range(n):
		ub = min(n,i+a[i]+1)
		lb = max(0,i-a[i])
		b[lb] += 1
		b[ub] -= 1
	for i in range(1,n):
		b[i] += b[i-1]
	a = b[::]
	a.pop()
	if(sum(a) == n*n):
		break
print(*a)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
imos = [0 for _ in range(n+1)]
"""
座標xに光の強さdの電球→[x-d, x+d] てらす
強さ0でもそれには適用.
"""
for _ in range(k):
	imos = [0 for _ in range(n+1)]
	for i in range(n):
		imos[max(i-a[i], 0)] += 1
		imos[min(i+a[i]+1, n)] -= 1
	cnt = 0
	alln = 0
	for i in range(n):
		cnt += imos[i]
		a[i] = cnt
		if a[i] == n:
			alln += 1
	if alln == n:
		break
print(*a)

Submission status: Accepted

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

M=[N]*N

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
        
    S=0
    for j in range(N):
        S+=L[j]
        A[j]=S

    if A==M:
        break

for i in range(N):
    print(A[i],end=" ")
print()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

print(*A)

Submission status: Accepted

Solution code:
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))


def test(A, K):
    A = list(A)
    for _ in range(K):
        B = [0] * N
        for i in range(N):
            b = 0
            for j in range(N):
                if A[j] >= abs(j - i):
                    b += 1
            B[i] = b
        A = B
    print(*A)
    return A


def test2(A, K):
    A = list(A)
    for _ in range(K):
        B = [0] * N
        for i in range(N):
            for j in range(N):
                if A[i] >= abs(j - i):
                    B[j] += 1
        A = B
    print(*A)
    return A


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


def solve(A, K):
    prev = A
    for _ in range(K):
        imos = [0] * (N + 1)
        for i in range(N):
            imos[max(0, i - A[i])] += 1
            imos[min(N, i + A[i] + 1)] -= 1
        prev = A
        A = cumsum(imos)[:-1]
        if prev == A:
            break
    print(*A)


# test(A,K)
# test2(A,K)

# N = len(A)
# for k in range(1000):
#     test(A, k)
solve(A, K)

Submission status: Accepted

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

Submission status: Accepted

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

#N = 200000
#A = [0]*N
#K = N

for i in range(K):
    diff = [0] * (N+2)
    for n, a in enumerate(A):
        n += 1
        l = max(1,n-a)
        r = min(N+1,n+a+1)
        diff[l] += 1
        diff[r] -= 1
    B = [0]
    for d in diff:
        B.append(B[-1] + d)
    A = B[2:-1]
    if sum(A) == N * N:
        break

print(*A)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    s = [0]*n
    for i,d in enumerate(a):
        if d==0:
            s[i] += 1
            if i+1<=n-1:
                s[i+1] -= 1
        else:
            s[max(0,i-d)] += 1
            if i+d+1<=n-1:
                s[min(n-1, i+d+1)] -= 1
    ss = [0]*n
    tmp = 0
    for i,num in enumerate(s):
        tmp += num
        ss[i] = tmp
    if all(t==v for t,v in zip(a,ss)):
        break
    a = ss
    
write(" ".join(map(str, a)))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
now = list(map(int,input().split()))
#import heapq
for _ in range(k):
  last = now
  now = []
  imos = [0 for _ in range(n+1)]
  for i in range(n):
    l = max(0,i-last[i])
    r = min(n,i+last[i]+1)
    imos[l] += 1
    imos[r] -= 1
  now.append(imos[0])
  for i in range(1,n):
    now.append(now[-1]+imos[i])
  #print(now)
  if sum(now) == n**2:
    print(' '.join(map(str,now)))
    exit()
print(' '.join(map(str,now)))

Submission status: Accepted

Solution code:
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,k=MI()
    a=LI()
    for _ in range(k):
        na=[0]*(n+1)
        for i in range(n):
            l=max(0,i-a[i])
            r=min(n,i+a[i]+1)
            na[l]+=1
            na[r]-=1
        if na[0]==n and na[-1]==-n:
            a=[n]*n
            break
        for i in range(n):
            na[i+1]+=na[i]
        a=na
    print(*a[:n])

main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

while K and sum(A) < N * N :
  l = [0] * N
  h = []
  for i in range(N) :
    while h and h[0] < i :
      heappop(h)
    l[i] = len(h)
    heappush(h, (i + A[i]))
    
  r = [0] * N
  h = []
  for i in range(N - 1, -1, -1) :
    while h and h[0] < -i :
      heappop(h)
    r[i] = len(h)
    heappush(h, (-(i - A[i])))
    
  for i in range(N) :
    A[i] = l[i] + r[i] + 1
    
  K -= 1
  
print(*A)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
from decimal import *
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n, k = MAP()
a = LIST()
for j in range(k):
    prea = [i for i in a]
    num = [0 for _ in range(n + 2)]
    for i in range(n):
        l = max(1, i + 1 - a[i])
        r = min(n + 1, i + 1 + a[i] + 1)
        num[l] += 1
        num[r] -= 1
    for i in range(1, n + 2):
        num[i] += num[i - 1]
    #print(num)
    a = [i for i in num[1:n + 1]]
    if a == prea:
        break
a = [str(i) for i in a]
print(' '.join(a))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k,*a = map(int,read().split())

from itertools import accumulate

if k >= 100:
    print(*[n]*n)

else:
    for _ in range(k):
        na = [0]*n
        for i,ai in enumerate(a):
            na[max(0,i-ai)] += 1
            if i+ai+1 < n:
                na[i+ai+1] -= 1
        a = accumulate(na)

    print(*list(a))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

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

K = min(100, K)
while K:
    K -= 1
    table = [0]*(N+1)
    for i in range(N):
        a = A[i]
        table[max(0, i-a)] += 1
        table[min(N, i+a+1)] -= 1
    
    for i in range(1, N):
        table[i] += table[i-1]
    
    A = table[:-1]

print(*A)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

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

for tests 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))
    flag=1
    for i in range(N):
        if A[i]<N:
            flag=0
        A[i]=min(A[i],N)

    if flag:
        break
    #print(A)

print(*A[:N])

Submission status: Accepted

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

if k > 200:
    k = 200

for i in range(k):
    new = [0] * n
    diff = [0] * n
    
    for j in range(n):
        diff[max(0, j - a[j])] += 1
        if j + a[j] + 1 < n:
            diff[j + a[j] + 1] -= 1

    for j in range(n):
        new[j] = diff[j] + new[j - 1]
    
    a = new
    
print(' '.join(map(str,a)))

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(n):
        b[i + 1] += b[i]
    a = b[:-1].copy()
    for x in a:
        if x < n:
            break
    else:
        print(*a)
        exit(0)
print(*a)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
lsn = a[:]
for _ in range(k):
  lsc = lsn[:]
  lsn = [0]*(n+1)
  for i in range(n):
    x = lsc[i]
    lsn[max(0,i-x)] += 1
    lsn[min(n,i+x+1)] -= 1
  for i in range(1,n+1):
    lsn[i] += lsn[i-1]
  if lsn.count(n) == n:
    break
print(*lsn[:n])

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:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    for _ in range(K):
        new = [0] * N
        imos = [0] * N
        for i, a in enumerate(A):
            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 = new
        if sum(A) == N * N:
            break
    print(*A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

while k!=0:
    B=[0 for _ in range(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(1,n):
        B[i] +=B[i-1]
    A=B[:n]
    k -=1
    if A==C:break
print(*A)

Submission status: Runtime Error

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

for _ in range(min(K, 50)):
    lamp = [0 for i in range(N + 1)]
    for i in range(N):
        lamp[max(0, i - A[i])] += 1
        lamp[min(N, i + A[i] + 1)] -= 1

    for i in range(N):
        lamp[i] += lamp[i - 1]
    A = lamp

[print(A[i], end=' ') for i in range(N)]
print()

Submission status: Runtime Error

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

for _ in range(min(K, 50)):
    lamp = [0 for i in range(N + 1)]
    for i in range(N):
        lamp[max(0, i - A[i])] += 1
        lamp[min(N, i + A[i] + 1)] -= 1

    for i in range(N):
        lamp[i] += lamp[i - 1]
    A = lamp

[print(A[i], end=' ') if i != N - 1 else print(A[i]) for i in range(N)]

Submission status: Runtime Error

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

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

    ans = 0
    for i in range(N):
        ans += lamp[i]
        A[i] = min(ans, N)

[print(A[i], end=' ') if i != N - 1 else print(A[i]) for i in range(N)]

Submission status: Runtime Error

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

while l < min(k,50):
  count = [0]*n
  for i in range(n):
    for j in range(-A[i],A[i]+1):
      if 0 <= i + j <= n-1:
        count[i+j] += 1
  A = count  

print(A)

Submission status: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

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

    # 全部0の最遅ケースでもlog(N)*2くらいで収束する log(2*10**5)<50
    for _ in range(min(K, 50)):
        tmp = [0] * (N + 1)
        b = [0] * (N + 1)
        for i in range(N):
            tmp[max(i - A[i], 0)] += 1
            tmp[min(i + A[i] + 1, N)] -= 1
        for i in range(N):
            A[i] = tmp[i] + b[i]
        # print(A)

    print(*A)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

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

    # 端っこだけ1の最遅ケースでもn**2オーダーで収束する
    for _ in range(min(K, N ** 0.5)):
        tmp = [0] * (N + 1)
        b = [0] * (N + 1)
        for i in range(N):
            tmp[max(i - A[i], 0)] += 1
            tmp[min(i + A[i] + 1, N)] -= 1
        for i in range(N):
            b[i+1] = tmp[i] + b[i]
        for i in range(N):
            A[i] = b[i+1] 

    print(*A)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(min(K, 50)):
    for i in range(N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        B[l] += 1
        if r + 1 < N:
            B[r+1] -= 1
    # 累積和
    for i in range(1, N):
        B[i] += B[i-1]
    A = B.copy()
   
for b in B:
    print(b, end=" ")

Submission status: Runtime Error

Solution code:
from numba import njit

@njit(parallel=True)
def solve(A):
    ans = [0] * (N + 1)
    for j in range(K):
        ans = [0] * (N + 1)
        for i in range(N):
            L = max(0, i - A[i])
            R = min(N, i + A[i] + 1)
            ans[L] += 1
            ans[R] -= 1
        for i in range(1, N + 1):
            ans[i] += ans[i - 1]
        issame = True
        for i in range(N):
            if i != 0:
                if ans[i - 1] != N or ans[i - 1] != ans[i]:
                    issame = False
            A[i] = ans[i]
        if issame:
            break
    for i in range(N):
        print(ans[i], end=' ')

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

solve(A)

Submission status: Runtime Error

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

@njit
def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

    m=n
    log = 0
    while m >= 2:
        m = m // 2
        log += 1
    from itertools import accumulate

    for i in range(min(k,n*2*log+1)):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            #if val==0: continue
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        A=list([0]+list(accumulate(B)))[1:]
    
    

    print(*A[:-1])    
    
    
resolve()

Submission status: Runtime Error

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

@jit
def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

    m=n
    log = 0
    while m >= 2:
        m = m // 2
        log += 1
    from itertools import accumulate

    for i in range(min(k,n*2*log+1)):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            #if val==0: continue
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        A=list([0]+list(accumulate(B)))[1:]
    
    

    print(*A[:-1])    
    
    
resolve()

Submission status: Runtime Error

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

@njit
def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

    m=n
    log = 0
    while m >= 2:
        m = m // 2
        log += 1
    from itertools import accumulate

    for i in range(min(k,n*2*log+1)):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            #if val==0: continue
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        A=list([0]+list(accumulate(B)))[1:]
    
    

    print(*A[:-1])    
    
    
resolve()

Submission status: Runtime Error

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

@njit
def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

    m=n
    log = 0
    while m >= 2:
        m = m // 2
        log += 1
    from itertools import accumulate

    for i in range(min(k,n*2*log+1)):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            #if val==0: continue
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        A=list([0]+list(accumulate(B)))[1:]
    
    

    print(*A[:-1])    
    
    
resolve()

Submission status: Runtime Error

Solution code:
import numpy as np
import math
n, k= [int(k) for k in input().split()]
a = np.array([int(k) for k in input().split()], dtype=np.int32)
for _ in range(k):
    b = np.zeros(n, dtype=np.int32)
    for i in range(n):
        l = math.ceil(i + 1 - a[i] - 0.5)
        r = int(i + 1 + a[i] + 0.5)
        for j in range(max(1, l), min(n + 1, r + 1)):
            b[j - 1] += 1
    a = b
print(" ".join([str(k) for k in a]))

Submission status: Runtime Error

Solution code:
from numba import njit
import numpy as np
 
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
@njit
for k in range(K):
  B = [0]*N
  for i in range(N): 
    start = max(0, i-A[i])
    end = min(N, i+A[i]+1)
    B[start] += 1
    if end <= N - 1:
      B[end] -= 1
  B = np.cumsum(B)
  #for i in range(1, N):
    #B[i] = B[i-1] + B[i] 
  A = B
  if min(A) == N:
    break
 
print(*A)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from numba import jit


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

#B = [0]*N                                 # 記録用のリスト

@jit
def main():
  for k in range(min(42, K)):                        # 以降の操作をK回繰り返す
    B = [0 for _ in range(N)] 
    for i in range(N):                      # 各電球によって照らされる範囲を考える
      start = max(0, i-A[i])                # 始点のインデックスは0かi-A[i]
      end = min(N, i+A[i]+1)                # 終点のインデックスはNかi+A[i]+1
      B[start] += 1                         # 始点に+1を記録する
      if end <= N - 1:
        B[end] -= 1                         # 終点に電球が存在する場合は-1を記録する
    amin = B[0]
    A[0] = B[0] 
    for i in range(1, N):                   # 累積和の計算
      A[i] = B[i-1] + B[i]
      amin = min(A[i], amin)
    if amin == N:                        # すべての電球がN個の電球に照らされるタイミングでbreakする
      break

  print(*A)                                 # リストAの中身を順に表示

main()

Submission status: Runtime Error

Solution code:
from numba import jit


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

#B = [0]*N                                 # 記録用のリスト

@jit
for k in range(min(42, K)):                        # 以降の操作をK回繰り返す
  B = [0 for _ in range(N)] 
  for i in range(N):                      # 各電球によって照らされる範囲を考える
    start = max(0, i-A[i])                # 始点のインデックスは0かi-A[i]
    end = min(N, i+A[i]+1)                # 終点のインデックスはNかi+A[i]+1
    B[start] += 1                         # 始点に+1を記録する
    if end <= N - 1:
      B[end] -= 1                         # 終点に電球が存在する場合は-1を記録する
  amin = B[0]
  A[0] = B[0] 
  for i in range(1, N):                   # 累積和の計算
    A[i] = B[i-1] + B[i]
    amin = min(A[i], amin)
  if amin == N:                        # すべての電球がN個の電球に照らされるタイミングでbreakする
    break

print(*A)                                 # リストAの中身を順に表示