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:
def solve(n, k, a_list):

    for t in range(k):

        left_list = [0] * n
        right_list = [0] * n

        for i in range(n):
            left = i - a_list[i] - 1
            if left >= 0:
                left_list[left] += 1
            right = i + a_list[i] + 1
            if right < n:
                right_list[right] += 1

        a_list = [n] * n

        if sum(left_list) == 0 and sum(right_list) == 0:
            break

        # right
        right_erase = 0
        for i in range(n):
            right_erase += right_list[i]
            a_list[i] -= right_erase
        # left
        left_erase = 0
        for i in range(n - 1, -1, -1):
            left_erase += left_list[i]
            a_list[i] -= left_erase

    return " ".join([str(a) for a in a_list])


def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    res = solve(n, k, a_list)
    print(res)


def test():
    assert solve(5, 1, [1, 0, 0, 1, 0]) == "1 2 2 1 2"
    assert solve(5, 2, [1, 0, 0, 1, 0]) == "3 3 4 4 3"


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]

class BIT():#添字は1から始まることに注意
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        for i,x in enumerate(seq,1):
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += x
            i += i & -i
    
    def find_kth_element(self,k):#k番目（最小は１）の要素
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
 
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = list(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    bit=[0]*(N+2)
    for i,a in enumerate(A):
        i+=1
        left=max(i-a,0)
        right=min(i+a+1,N+1)
        bit[left]+=1
        bit[right]-=1
    
    for k in range(K):
        update=[0]*N
        nA=copy(A)
        ax=accumulate(bit)
        #print(bit)
        #next(ax)
        next(ax)
        for i in range(N):
            a=A[i]
            na=next(ax)
            #print(na)

            if a!=na:
                nA[i]=na
                update[i]=1


        #print(A)
        if sum(update)==0:
            break

        for i, a in enumerate(A):
            if update[i]==0:
                continue
            na=nA[i]
            i+=1

            left=max(i-a,0)
            right=min(i+a+1,N+1)
            bit[left]-=1
            bit[right]+=1
            left=max(i-na,0)
            right=min(i+na+1,N+1)
            bit[left]+=1
            bit[right]-=1

        A=nA
    
    print(*nA)

        





if __name__ == "__main__":
    main()

Submission status: Accepted

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

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    for cnt in range(min(k, 41)):
        ans = []
        bit = [0]*(n+1)
        for i, j in enumerate(a):
            x, y = max(i-j, 0)+1, min(i+j+1, n)+1
            while x < n+1:
                bit[x] += 1
                x += x & (-x)
            while y < n+1:
                bit[y] -= 1
                y += y & (-y)
        for i in range(n):
            ret, x = 0, i+1
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            ans.append(ret)
        a = ans

    print(*ans)


main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
imos = [0]*(2*10**5+1)
for j in range(min(k,700)):
    imos = [0]*(2*10**5+1)
    for i in range(n):
        imos[max(i-a[i],0)] += 1
        imos[min(i+a[i]+1,2*10**5)] -= 1
    for i in range(1,n):
        imos[i] += imos[i-1]
    a = imos
print(*imos[:n])

Submission status: Accepted

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

S = A
D = [0] * N
for _ in range(K):
  for x in range(N):
    D[x] = 0
  for x in range(N):
    D[max(0, x - S[x])] += 1
    if(x + S[x] + 1 < N):
      D[x + S[x] + 1] -= 1
  S[0] = D[0]
  for x in range(1, N):
    S[x] = S[x-1] + D[x]
  if all([x == N for x in S]):
    break
      
print(' '.join([str(x) for x in S]))

Submission status: Accepted

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


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

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

Submission status: Accepted

Solution code:
def Next(a):
    global n
    print(a)
    hajimari=[0]*n
    owari=[0]*n
    for i in range(n):
        hidari=i-a[i]-1
        migi=i+a[i]+1
        if(hidari>=0):
            hajimari[hidari]+=1
        if(migi<n):
            owari[migi]+=1
    print(hajimari)
    print(owari)
    for i in range(n-1):
        hajimari[n-i-2]+=hajimari[n-i-1]
    for i in range(n-1):
        owari[i+1]+=owari[i]
    print(hajimari)
    print(owari)

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

k=min(300,k)

for i in range(k):
    #print(a)
    hajimari=[0]*n
    owari=[0]*n
    for i in range(n):
        hidari=i-a[i]-1
        migi=i+a[i]+1
        if(hidari>=0):
            hajimari[hidari]+=1
        if(migi<n):
            owari[migi]+=1
    #print(hajimari)
    #print(owari)
    for i in range(n-1):
        hajimari[n-i-2]+=hajimari[n-i-1]
    for i in range(n-1):
        owari[i+1]+=owari[i]
    #print(hajimari)
    #print(owari)
    for i in range(n):
        a[i]=n-hajimari[i]-owari[i]

s=[]
for i in range(n):
    s.append(str(a[i]))

print(" ".join(s))

Submission status: Accepted

Solution code:
import collections
n,k = map(int, raw_input().split(' '))
ais = map(int ,raw_input().split(' '))

prev = ais[::]
for _ in range(k):

	h = collections.Counter()
	for i,d in enumerate(ais):
		u = i+1
		h[max(1, u - d)] += 1
		h[u + d + 1] -= 1

	cumul = 0
	for u in range(1, n+1):
		cumul += h[u]
		ais[u - 1] = cumul
	if prev == ais[::]:
		break
	prev = ais[::]


for e in ais:print e,

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 i in range(n):
        if a[i]:
            b[max(0,i-a[i])] += 1
            b[i] -= 1
            b[i+1] += 1 
            b[min(n,i+a[i]+1)] -= 1
    b[0] += 1
    count = b[0]
    for i in range(1,n):
        b[i] += b[i-1]
        count += b[i]
    a = b[:n]
    if count == n*n:
        print(*a)
        exit()
print(*a)

Submission status: Accepted

Solution code:
from copy import copy
n, k = map(int, input().split())
ns = list(map(int, input().split()))
for i in range(k):
    imosur = [0] * n
    imosul = [0] * n
    ans = [0] * n
    for i in range(n):
        imosur[i] += 1
        if i + ns[i] + 1 < n:
            imosur[i + ns[i] + 1] -= 1
        imosul[n - i - 1] += 1
        if n - i - 2 - ns[n - i - 1] >= 0:
            imosul[n - i - 2- ns[n - i -1]] -= 1
    r=0
    l=0
    for i in range(n):
        r += imosur[i]
        ans[i] += r
        l += imosul[n - i - 1]
        ans[n - i - 1] += l - 1
    if min(ans) == n:
        print(*[n for _ in range(n)])
        exit()
    ns = copy(ans)
print(*ans)

Submission status: Accepted

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

if K > 40:
  print(*[N for _ in range(N)])
  quit()

def f(A):
    table = [0]*(N+1)
    for i, v in enumerate(A):
        d = A[i]
        table[max(0, i-d)] += 1
        table[min(N, i+d+1)] -= 1

    cumsum = [table[0]]
    for i in range(1, N):
        cumsum.append(cumsum[-1]+table[i])
    return cumsum

for i in range(K):
    A = f(A)
print(*A)

Submission status: Accepted

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

for i in range(K):
    P = [0 for _ in range(N)] + [0]
    for j in range(N):
        P[max(0, j - A[j])] += 1
        P[min(N, j + A[j] + 1)] -= 1
    A = [0 for _ in range(N)]
    for j in range(N):
        P[j + 1] += P[j]
    flag = False
    for j in range(N):
        A[j] = P[j]
        if A[j] < N:
            flag = True
    if not flag:
        break

print(*A)

Submission status: Accepted

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

i = 0
for _ in range(min(K, 50)):
    B = [0] * (N + 1)
    for i, a in enumerate(A):
        j = max(0, i - a)
        B[j] += 1
        j = min(N, i + a + 1)
        B[j] -= 1
    B.pop()
    A = list(accumulate(B))

print(*A)

Submission status: Accepted

Solution code:
import copy
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(min(100,k)):
  L1=[0]*(n+2)
  if i!=0:
    a=L2[1:n+1]
  for j in range(n):
    L1[max(j-a[j],0)]+=1
    L1[min(j+a[j],n)+1]-=1
  L2=[0]
  for i in range(n+2):
    L2.append(L2[-1]+L1[i])
a=L2[1:n+1]
for i in range(len(a)):
  a[i]=str(a[i])
print(' '.join(a))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = map(int, input().split())
a = list(map(int, input().split()))
# A = 0, 0, 0, ..., 0でも最小値は2^(N-1)で増える
# k > 50くらいでnを超えるのでそれくらいまで考えればよい
def print_ans(ans):
   ans = list(map(lambda x: str(x) if x <= n else str(n), ans))
   print(" ".join(ans))

all_max = [n] * n
if k > 50:
   print_ans(all_max)
   exit()

# k < 50の時はimos法でO(N*k)くらいで求まりそう

for _ in range(k):
   pre_a = a[:]
   imos = [0 for _ in range(n+1)]
   for i in range(n):
      l = max(0, i - pre_a[i])
      r = min(n, i + pre_a[i] + 1)
      imos[l] += 1
      imos[r] -= 1
   # process
   v = 0
   for i in range(n):
      v += imos[i]
      if v > n:
         v = n
      a[i] = v
print_ans(a)

Submission status: Accepted

Solution code:

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

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

#n = 2 * 10 ** 5
#a = [0] * n
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:
        break
print(*a)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(k):
    accu = [0]*(n+1)
    for i in range(n):
        accu[max(i-a[i], 0)] += 1
        accu[min(i+a[i]+1, n)] -= 1
    now = 0
    for i in range(n):
        now += accu[i]
        a[i] = now
    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()))
B = A.copy()
k = 0
while k < K and sum(B) < N**2:
  tmp = [0]*N
  i = 0
  while i < N:
    a = B[i]
    tmp[max(0, i-a)] += 1
    if i+a+1 < N:
      tmp[i+a+1] -= 1
    i += 1
  s = 0
  i = 0
  while i < N:
    B[i] = tmp[i]+s
    s = B[i]
    i += 1
  k += 1
print(" ".join([str(b) for b in B]))

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

K = min(100, K)

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

    for j in range(1, N):
        B[j] += B[j - 1]
    A = B[:-1]

print(*A)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
from sys import stdin
input = stdin.readline
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
a = inl()
for kk in range(k):
    l = [0]*n
    r = [0]*(n+1)
    for j in range(n):
        l[max(0,j-a[j])] += 1
        r[min(n,j+a[j]+1)] += 1
    cnt = 0
    mn = BIG
    for j in range(n):
        cnt += l[j]-r[j]
        a[j] = cnt
        mn = min(mn,cnt)
    if mn==n:
        break
pad = ''
for j in range(n):
    printn(pad+str(a[j]))
    pad = ' '
print('')

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

print(*A)

Submission status: Accepted

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

def main():
    N,K = map(int,input().split())
    a = [0] + list(map(int,input().split())) + [0]
    
    for i in range(K):
        imos = [0]*(N+2)
        for j in range(1,N+1):
            num = a[j]
            imos[max(j-num,0)] += 1
            imos[min(j+num+1,N+1)] -= 1
        for j in range(N+1):
            imos[j+1] = imos[j]+imos[j+1]
        imos[0] = 0
        a = imos
        if sum(a[1:N+1]) == N**2:
            break
    
    print(*a[1:N+1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(min(K,41)):
    l=[0]*(N+1)
    c=0
    for j in range(N):
        if j-A[j]>0:
            l[j-A[j]]+=1
        else:
            c+=1
        if A[j]+j<N:
            l[A[j]+j+1]-=1 
    for j in range(N):
        c+=l[j]
        A[j]=c
print(*A)

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys
input = sys.stdin.readline
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n,k = ip()
x = ip()
for _ in range(k):
    dp = [0]*(n+1)
    for i in range(n):
        pos1 = max(i-x[i],0)
        pos2 = min(i+x[i]+1,n)
        dp[pos1] += 1
        dp[pos2] -= 1
    for i in range(1,n+1):
        dp[i] += dp[i-1]
    if x == dp:
        break
    x = list(dp)
print(*x[:-1])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, floor
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np

N, K = MAP()
A = LIST()

cnt = 0
while 1:
	a = [0]*(N+1)
	flg = 1
	for i in range(N):
		a[max(0, i-A[i])] += 1
		a[min(N, i+A[i]+1)] -= 1
		if max(0, i-A[i]) == 0 and min(N, i+A[i]+1) == N:
			flg *= 1
		else:
			flg *= 0
	A = list(accumulate(a))
	cnt += 1
	if cnt == K:
		print(*A[:-1])
		exit()
	if flg:
		break

A = [N]*N
print(*A)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    import copy
    # import numpy as np
    # import math
    # import random
    input = stdin.readline

    n, k = map(int, input().split())
    aa = list(map(int, input().split()))
    # n = 200000
    # k = 49
    # aa = [0]*n
    # aa = [0]*n
    if k >= 50:
        str_n = str(n)
        ans = [str_n]*n
        print(' '.join(ans))
        exit()
    copy_aa = copy.deepcopy(aa)
    next = [0]*n  
    for _ in range(k):
        calculation_list = [0]*(n+1)
        for index, a in enumerate(copy_aa):
            section_min = index-a if index-a>=0 else 0
            section_max = index+a+1 if index+a+1<=n else n
            calculation_list[section_min] += 1
            # print(section_max)
            calculation_list[section_max] -= 1
        now = 0
        for index, calculation in enumerate(calculation_list[:-1]):
            now += calculation
            copy_aa[index] = now
        # copy_aa = copy.deepcopy(next)
        # next = [0]*n
    print(' '.join(map(str, copy_aa)))

Submission status: Accepted

Solution code:
from __future__ import print_function
import sys


if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve(a):
    for j in range(k):
        el = [0] * n
        er = [0] * n
        for i in range(n):
            el[max(i - a[i], 0)] += 1
            er[min(i + a[i], n-1)] += 1
        a = [0]*n
        a[0] = el[0]
        all_n = True
        for i in range(1, n):
            a[i] = a[i-1] + el[i] - er[i-1]
            all_n &= a[i] == n
        if all_n:
            print(*a)
            return
    print(*a)
    return







n, k = RA()
a = RA()
solve(a)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    key = 50
    nn = n
    while nn > 0:
        key += 1
        nn //= 2
    
    for _ in range(min([key, k])):
        b = [0]*n
        for i in range(n):
            l, r = max([i-a[i], 0]), min([i+a[i], n-1])
            b[l] += 1
            if r != n-1:
                b[r+1] -= 1
        for i in range(n):
            a[i] = 0
            a[i] += b[i]
            if i != 0:
                 a[i] += a[i-1]
    print(*a)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
for _ in range(k):
    lst = [0]*(n+1)
    for i in range(n):
        lst[max(i - a[i], 0)] += 1
        lst[min(i + a[i] + 1, n)] -= 1
    a = list(accumulate(lst))[:-1]
    for i in range(n):
        if a[i] != n:
            break
    else:
        print(*a)
        quit()
print(*a)

Submission status: Accepted

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

def one_term(lis):
    imos = [0] * n

    for i, a in enumerate(lis):
        left = max(0, i - a)
        right = min(n, i + a + 1)
        imos[left] += 1
        try:
            imos[right] -= 1
        except:
            pass
    return list(ac(imos))

ans = A
for i in range(k):
    ans = one_term(ans)
    if ans.count(n) == n:
        break
print(*ans, sep=" ")

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *
def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1/f

def make_next(n, nums):
    imos = [0 for i in range(n)]
    for i, num in enumerate(nums):
        if num > i:
            imos[0] += 1
        else:
            imos[i - num] += 1

        if i + num + 1 < n:
            imos[i+num+1] -= 1
    # print(imos)
    nx = []
    tmp = 0
    for im in imos:
        tmp += im
        nx.append(tmp)

    return nx

def mantan_check(n, nums):
    if sum(nums) == n ** 2:
        return True
    else:
        return False

def solve():
    n, k = getList()
    nums = getList()
    for i in range(k):
        nums = make_next(n, nums)
        if mantan_check(n, nums):
            print(*nums)
            return

    print(*nums)
    return



def main():
    # n = getN()
    # for _ in range(n):
    solve()
if __name__ == "__main__":
    solve()

"""
5 10000000000000
4 0 0 0 0
"""

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    ans = S[:3]
    print(ans)
    return

def examB():
    A, V = LI()
    B, W = LI()
    T = I()
    L = abs(A-B)
    v = V-W
    if v*T>=L:
        ans = "YES"
    else:
        ans = "NO"
    print(ans)
    return

def examC():
    N, K = LI()
    A = LI()
    for _ in range(min(60,K)):
        cur = N
        L = [0] * (N + 1)
        R = [0] * (N + 1)
        for i in range(N):
            a = A[i]
            if 0<i-a:
                L[i-a] += 1
            else:
                L[0] += 1
            if N>i+a+1:
                R[i+a+1] += 1
            else:
                R[N] += 1
            if cur>a:
                cur = a
        if cur==N:
            break
        A[0] = L[0]
        for i in range(1,N):
            A[i] = A[i-1]+L[i]-R[i]


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

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, A: "List[int]"):
    #while True:
    for _ in range(K):
        inc = [0] * N
        dec = [0] * N
        for i in range(N):
            s = max(0, i - A[i])
            e = min(N - 1, i + A[i])
            inc[s] += 1
            dec[e] += 1
        nexts = []
        cur = 0
        found = False
        for i in range(N):
            cur += inc[i]
            if cur < N:
                found = True
            nexts.append(cur)
            cur -= dec[i]
        A = nexts
        if not found:
            break
    print(*A, sep=' ')
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, 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):
    b=[0]*(n+1)
    for i in range(n):
        b[max(i-a[i],0)]+=1
        b[min(i+a[i]+1,n)]-=1
    for i in range(n):
        b[i+1]+=b[i]
    f=1
    for j in range(n):
        if b[j]!=n:
            f=0
            break
    if f:
        print(*b[:n])
        exit()
    a=b[:]
print(*a[:n])

Submission status: Accepted

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

count=0
while True and K>count:
    nx=[0]*N
    for i in range(N):
        posl=max(0,i-A[i])
        posr=min(N-1,i+A[i])
        if N-1>posr:
            nx[posl]+=1
            nx[posr+1]-=1
        else:
            nx[posl]+=1
    for i in range(1,N):
        nx[i]+=nx[i-1]
    A=nx
    count+=1
    if min(A)==N:
        break

print(*A)

Submission status: Accepted

Solution code:
n,k=[int(j)for j in input().split()]
a=[int(j)for j in input().split()]
if n<=k:
    print(*[n]*n)
    exit()
import copy
for idx in range(k):
    table=[0]*n
    for i in range(n):
        table[max(i-a[i],0)]+=1
        if i+a[i]+1<n:
            table[i+a[i]+1]-=1
    for i in range(1,n):
        table[i]+=table[i-1]
    a=copy.deepcopy(table)
    if a==[n]*n:
        break
print(*a)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(K):
    d=[0]*(N+1)
    for j,a in enumerate(A):
        d[max(0,j-a)]+=1
        d[min(N,j+a+1)]-=1
    b=1
    for j in range(N):
        if d[j]!=N:
            b=0
        d[j+1]+=d[j]
    A=d[:-1]
    if b>0:
        break
print(*A)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
import copy
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	if K >= 40:
		ans = [N] * N
		print(*ans)
		return

	for i in range(K):
		imos = [0] * (N + 1)
		for j in range(N):
			left = max(0, j - A[j])
			right = min(N, j + A[j] + 1)
			imos[left] += 1
			imos[right] -= 1

		for j in range(N):
			imos[j + 1] += imos[j]

		A = copy.deepcopy(imos[:-1])

	print(*A)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0 for i in range(n+1)]
b.append(0)
for i in range(k):
    for j in range(n):
        if a[j] > j and a[j] + j + 1 > n:
            b[0] += 1
            b[-1] -= 1
        if a[j] > j and a[j] + j + 1 <= n:
            b[0] += 1
            b[j+a[j]+1] -= 1
        if a[j] <= j and a[j] + j + 1 > n:
            b[j-a[j]] += 1
            b[-1] -= 1
        if a[j] <= j and a[j] + j + 1 <= n:
            b[j-a[j]] += 1
            b[j+a[j]+1] -= 1
    for j in range(1,n):
        b[j] += b[j-1]
    for j in range(n):
        a[j] = b[j]
    if b.count(n) == n:
        break
    for j in range(n):
        a[j] = b[j]
    b = [0 for i in range(n+1)]
print(*a)