Problem:


Score : 500 points

Problem Statement

We have N bulbs arranged on a number line, numbered 1 to N from left to right.
Bulb i is at coordinate i.

Each bulb has a non-negative integer parameter called intensity.
When there is a bulb of intensity d at coordinate x, the bulb illuminates the segment from coordinate x-d-0.5 to x+d+0.5.
Initially, the intensity of Bulb i is A_i. We will now do the following operation K times in a row:

For each integer i between 1 and N (inclusive), let B_i be the number of bulbs illuminating coordinate i. Then, change the intensity of each bulb i to B_i.

Find the intensity of each bulb after the K operations.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq K \leq 2 \times 10^5

0 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

Print the intensity A{'}_i of each bulb i after the K operations to Standard Output in the following format:

A{'}_1 A{'}_2 \ldots A{'}_N

Sample Input 1

5 1
1 0 0 1 0

Sample Output 1

1 2 2 1 2 

Initially, only Bulb 1 illuminates coordinate 1, so the intensity of Bulb 1 becomes 1 after the operation.
Similarly, the bulbs initially illuminating coordinate 2 are Bulb 1 and 2, so the intensity of Bulb 2 becomes 2.

Sample Input 2

5 2
1 0 0 1 0

Sample Output 2

3 3 4 4 3 



Sample input:
5 1
1 0 0 1 0


Sample output:
1 2 2 1 2

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

##### 進数の変換 #####
# bin_str = bin(i)[2:]
# oct_str = oct(i)[2:]
# hex_str = hex(i)[2:]

##### とても大きな数 と 小数の計算誤差 #####
# 「Decimal」は計算誤差を 0にできる。必要に応じて粒度を設定せよ。
# getcontext().prec = 100
#
# tmp = Decimal(i)
# A,B = map(Decimal, input().split())
# ans = A * B

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	A = inputList()

	if N <= 2*K:
		T = [N for i in range(N)]
		print(*T)
		sys.exit()

	for j in range(K):
		T = [0 for i in range(N)]
		for i,val in enumerate(A):
			#print(T)
			tmp_min = max(0,i-val)
			T[tmp_min] += 1

			if i+val+1 > N-1:
				continue
			tmp_max = min(N-1,i+val+1)
			T[tmp_max] -= 1

		for i,val in enumerate(T):
			if i == 0:
				continue
			T[i] += T[i-1]
		A = T

	print(*A)



def segfunc(x, y):
    return 0

ide_ele = float('inf')

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# 2分検索のリバース
def bisect_left_reverse(a, x):
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

def bisect_right_reverse(a, x):
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# 2分検索
# 存在しない場合: None 存在する場合: その値
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return None

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
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+2)]
if K > 70:
    ans = [N for i in range(N)]
    print(*ans)
else:
    for _ in range(K):
        for i in range(N+2):
            b[i] = 0
        for i in range(N):
            b[max(0, i+1-A[i])] += 1
            b[min(N+1, i+1+A[i]+1)] -= 1
        for i in range(1, N+1):
            b[i] += b[i-1]
            A[i-1] = b[i]
    print(*A)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
if n == 1:
    print(1)
else:
    for _ in range(k):
        flag = 0
        imos = [0]*(n+1)
        for i,a in enumerate(A):
            imos[max(0,i-a)] += 1
            imos[min(n,i+a+1)] -= 1
        flag = (imos[0] != n)
        for i in range(n-1):
            imos[i+1] += imos[i]
            if imos[i+1] != n:
                flag = 1
        A = imos[:n].copy()
        if not flag:break
    print(' '.join(str(i) for i in A))

Submission status: Accepted

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

for i in range(k):
	im = [0 for _ in range(n+1)]
	for i, x in enumerate(a):
		im[max(i-x, 0)] += 1
		im[min(i+x+1, n)] -= 1
	nxt = [im[0]]
	for i in range(1, n):
		nxt.append(nxt[-1] + im[i])
	a = nxt
	if min(a) == n:
		break

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):
        start = [0] * N
        end = [0] * N
        for j in range(N):
            if j - A[j] < 0:
                start[0] += 1
            else:
                start[j-A[j]] += 1
            if j + A[j] >= N:
                pass
            else:
                end[j+A[j]] += 1
        tmp = start[0]
        A[0] = tmp
        tmp_min = tmp
        for j in range(1, N):
            tmp += start[j]
            tmp -= end[j-1]
            A[j] = tmp
            tmp_min = min(tmp_min, tmp)
        if tmp_min >= N:
            break
    print(" ".join(map(str, A)))

if __name__ == '__main__':
    main()

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()))
    #print(2**(k-1))
    if (k>50):
        ans = [n]*n
        print(*ans)
        exit()
    #print(tnp)
    for i in range(k):
        b = [0]*n
        for i in range(n):
            l = i-a[i]
            r = i+a[i]
            #print(l,r)
            b[max(l,0)] += 1
            if (r<n-1):
                b[r+1] -= 1
            #print(b)
    
        for i in range(1,n):
            b[i] = b[i-1] + b[i]
        a = b
        
    print(*b)
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
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

N, K = MAP()
A = LIST()
for cnt in range(K):
	tmp = [0]*(N+1)

	for i, a in enumerate(A):
		tmp[max(0, i-a)] += 1
		tmp[min(N, i+a+1)] -= 1
	tmp = list(accumulate(tmp))
	A = tmp[:-1]
	if all(x==N for x in A):
		break

print(*A)

Submission status: Accepted

Solution code:
#import numpy as np
N,K=map(int, input().split())

A=list(map(int, input().split()))
#K=min(K, 30)
for k in range(K):
    B=[0]*(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)
    A=[0]*N
    A[0]=B[0]
    for i in range(1,N):
        A[i]=A[i-1]+B[i]

    if min(A)==N:
        break
    #print(B)
    
    
print(*A)

Submission status: Accepted

Solution code:
from itertools import accumulate


def main():
    n, k = map(int, input().split())
    a = [int(i) for i in input().split()]
    ini = [0] * n
    fin = [n] * n
    for c in range(min(k, 45)):
        b = ini.copy()
        for i, ai in enumerate(a):
            b[max(i - ai, 0)] += 1
            if i + ai + 1 < n:
                b[i + ai + 1] -= 1
        a = list(accumulate(b))
    print(*a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().rstrip()

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

    for _ in range(K):
        new_A = [0] * (N)
        for i, a in enumerate(A):
            s = i - a
            if s < 0:
                s = 0
            f = i + a + 1
            new_A[s] += 1
            if f < N:
                new_A[f] -= 1
        A = list(accumulate(new_A))
        if min(A) == N:
            break
    print(*A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
Z=[n]*n
class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)
for _ in range(k):
    tree = BIT(n)
    for i in range(n):
        l = max(0,i-A[i])
        r = min(n,i+A[i]+1)
        #print(l,r)
        tree.add(l,r,1)
        #print([tree.get_val(i) for i in range(n)])
    A=[tree.get_val(i) for i in range(n)]
    #print(A)
    if A == Z:
        break
        #print(*Z)
print(*A)

Submission status: Accepted

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

readline = sys.stdin.readline

@njit('i8,i8,i8[::1]',cache=True)
def loop(n,k,a):
    for j in range(k):
        b = np.zeros(n+1, dtype=np.int64)
        for i in range(n):
            b[max(i-a[i], 0)] += 1
            b[min(i+a[i]+1, n)] -= 1
        a = np.cumsum(b)[:-1]
        if np.all(a==n):
            return(a)
            break
    else:
        return(a)


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

ans = loop(n,k,a)
print(*ans)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=list(map(int,readline().split()))

    cnt=0
    while cnt<k:
        s=[0]*n
        for i in range(n):
            x_min=i-a[i]
            x_max=i+a[i]+1
            s[max(0,x_min)]+=1
            if n-1<x_max:
                pass
            else:
                s[x_max]-=1
        a=list(accumulate(s))
        cnt+=1
        
        flag=True
        for i in range(n):
            if a[i]!=n:
                flag=False
                break
        if flag: break

    print(*a)

if __name__=="__main__":
    main()

Submission status: Accepted

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

for _ in range(k):
    f = 1
    for i in range(1, n+1):
        if a[i] != n:
            f = 0
            break
    if f:
        break
    memo = [0] * (n+1)
    for i in range(1, n+1):
        l = max(1, i-a[i])
        r = min(n, i+a[i])
        memo[l-1] += 1
        memo[r] += -1
    b = [0]
    for memoi in memo:
        b.append(b[-1]+memoi)
    a = b

print(" ".join(list(map(str, a[1:n+1]))))

Submission status: Accepted

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

while(True):
    p = 0
    T = [0]*N
    for i in range(N):
        T[max(i-A[i], 0)] += 1
        if i+A[i]+1 > N - 1:
            pass
        else:
            T[i+A[i]+1] -= 1
    for i in range(1,N):
        T[i] += T[i-1]
    c += 1
    if c == K:
        for i in range(N):
            print(T[i], end=" ")
        sys.exit()
    for i in range(N):
        if T[i] < N:
            p = 1
            break
    if p == 0:
        for i in range(N):
            print(N, end= " ")
        sys.exit()
    A = T[:]

Submission status: Accepted

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

# N = 10 ** 5 * 2
# K = N
# A = [0] * (N+1)

cnt = 0
while (A[0] < N or A[-1] < N) and cnt < K:
    cnt += 1
    next_A = [0] * (N+1)
    for j in range(N):
        tmp = A[j]
        next_A[max(j-tmp, 0)] += 1
        next_A[min(N, tmp+1+j)] -= 1
    for j in range(N):
        next_A[j+1] += next_A[j]
    next_A.pop()
    A = next_A
print(" ".join([str(i) for i in A]))

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


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

    # if sum(a)==0:
    #     print(*a)
    #     quit()
    while k:
        lst=[1]*n
        dic={}
        cnt=0
        for i in range(n):
            lst[i]+=cnt
            if i in dic:
                cnt-=dic[i]
            if a[i]>0:
                if not i+a[i] in dic:
                    dic[i+a[i]]=1
                else:
                    dic[i+a[i]]+=1
                cnt+=1

        dic={}
        cnt=0
        for i in range(n)[::-1]:
            lst[i]+=cnt
            if i in dic:
                cnt-=dic[i]
            if a[i]>0:
                if not i-a[i] in dic:
                    dic[i-a[i]]=1
                else:
                    dic[i-a[i]]+=1
                cnt+=1
        k-=1
        if sum(lst)==n*n:
            break
        # print(k)
        a=lst[:]

    print(*lst)

main()

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    if K >= 50: A = [N] * N
    else:
        for k in range(K):
            nextL = [0] * (N + 1)
            for i, a in enumerate(A):
               left = max(0, i - a)
               right = min(N, i + a + 1)
               nextL[left] += 1
               nextL[right] -= 1
            A[0] = nextL[0]
            for i in range(1, N):
                A[i] = A[i-1] + nextL[i]
    print(*A, sep=" ")
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import copy

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,k = na()
    a = na()
    memo = [0]*(n+1)
    for i in range(n):
        ai = a[i]
        memo[max(0, i-ai)] += 1
        memo[min(n, i+ai+1)] -= 1
    k -= 1
    if k == 0:
        tmp = 0
        for i in range(n):
            tmp += memo[i]
            print(tmp, end=' ')
        return
    while k != 0:
        flag = 0
        memo2 = [0]*(n+1)
        tmp = 0
        for i in range(n+1):
            tmp += memo[i]
            if tmp >= max(i, n-i-1):
                flag += 1
            memo2[max(0, i-tmp)] += 1
            memo2[min(n, i+tmp+1)] -= 1
        if flag == n:
            memo2[0] = n
            memo2[-1] = -1*n
            break
        memo = copy.copy(memo2)
        k -= 1
    tmp = 0
    for i in range(n):
        tmp += memo2[i]
        print(tmp, end=' ')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(K):
    a=[0 for i in range(N+1)]
    for j in range(N):
        a[max(0,j-L1[j])]+=1
        a[min(N,j+L1[j]+1)]-=1
        #print(a[:N])
    L2=[a[0]]
    for j in range(1,N):
        L2.append(L2[-1]+a[j])
    #print(L2)
    if L2==L1[:N]:
        print(*L2)
        exit()
    else:
        L1=L2+[0]
print(*L2)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    sa = sum(a)
    for i in range(k):
        mov = [0]*n
        for i,ai in enumerate(a):
            if i-ai >= 0:
                mov[i-ai] += 1
            else:
                mov[0] += 1
            if i+ai+1 < n:
                mov[i+ai+1] -= 1
        na = a*1
        sna = sa
        a[0] = mov[0]
        sa = mov[0]
        for i in range(1,n):
            a[i] = a[i-1]+mov[i]
            sa += a[i]
        if sna == sa:
            break
    print(" ".join(map(str,a)))

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
m1=list(map(int,input().split()))
m2=[]
imos=[0]*(n+1)
counter=0
while counter<=k:
  counter+=1
  if counter%2==1:
    m2=[]
    imos=[0]*(n+1)
    for i in range(n):
      imos[max(0,i-m1[i])]+=1
      imos[min(n,i+m1[i]+1)]-=1
    current=0
    for i in range(n):
      current+=imos[i]
      m2.append(current)
    sameflag=1
    for i in range(n):
      if m1[i]!=m2[i]:
        sameflag=0
        break
    if sameflag==1:
      for i in range(n):
        m2[i]=str(m1[i])
      print(' '.join(m2))
      sys.exit()
  else:
    m1=[]
    imos=[0]*(n+1)
    for i in range(n):
      imos[max(0,i-m2[i])]+=1
      imos[min(n,i+m2[i]+1)]-=1
    current=0
    for i in range(n):
      current+=imos[i]
      m1.append(current)
    for i in range(n):
      if m1[i]!=m2[i]:
        sameflag=0
        break
    if sameflag==1:
      for i in range(n):
        m2[i]=str(m1[i])
      print(' '.join(m2))
      sys.exit()
if k%2==0:
  for i in range(n):
    m2[i]=str(m1[i])
  print(' '.join(m2))
else:
  for i in range(n):
    m1[i]=str(m2[i])
  print(' '.join(m1))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0
# n = int(input())
# arr = [0 for _ in range(n)]
while True:
    cnt += 1
    new = [0 for _ in range(n)]
    for i in range(n):
        new[max(0, i-arr[i])] += 1

        tmp = i+arr[i]+1
        if tmp < n:
            new[tmp] -= 1

    flag = 1
    for i in range(1, n):
        new[i] += new[i-1]
        if new[i] < n:
            flag = 0

    arr = new
    # print(arr)
    if flag or cnt >= k:
        break
# print(cnt)
for i in arr:
    print(i, end=" ")

Submission status: Accepted

Solution code:
#imos法で更新を繰り返す
#log回で終わる
from itertools import accumulate
n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(k):
    b=[0]*n
    for i in range(n):
        b[max(0,i-a[i])]+=1
        if i+a[i]+1<n:
            b[i+a[i]+1]-=1
    a=list(accumulate(b))
    if a==[n]*n:
        break
    #print(a)
print(" ".join(map(str,a)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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


for i in range(K):
    nxtA = [0]*N
    imos_l = [0]*N
    imos_r = [0]*N

    for j in range(N):
        if A[j]>0:
            if j+1<N:
                imos_l[j+1] += 1
            if j+1+A[j]<N:

                imos_l[j+1+A[j]] -= 1
    for j in reversed(range(N)):
        if A[j]>0:
            if j-1>=0:
                imos_r[j-1] += 1
            if j-1-A[j]>=0:
                imos_r[j-1-A[j]] -= 1
    cur = 1
    for j in range(N):
        cur += imos_l[j]
        nxtA[j] += cur
    cur = 0
    for j in reversed(range(N)):
        cur += imos_r[j]
        nxtA[j] += cur
    # print(imos_l, imos_r)
    if sum(nxtA)==N*N:
        print(*nxtA)
        exit()
    if i<N-1:
        for j in range(N):
            A[j] = nxtA[j]

print(*nxtA)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
for _ in range(min(200,k)):
  tmp=[0]*n
  for i in range(n):
    if i+1<n:
      tmp[i+1]+=1
      if i+arr[i]+1<n:
        tmp[i+arr[i]+1]+=-1
    if i-1>=0:
      tmp[i]+=-1
      if i-arr[i]>=0:
        tmp[i-arr[i]]+=1
      else:
        tmp[0]+=1
  for i in range(1,n):
    tmp[i]+=tmp[i-1]
  for i in range(n):
    tmp[i]+=1
  arr=tmp
print(*arr)

Submission status: Accepted

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

for _ in range(k):
    b = [0] * (n + 2)
    for i in range(n):
        b[max(0, i - a[i])] += 1
        b[min(n + 1, i + a[i] + 1)] -= 1
    a[0] = b[0]
    cnt = a[0]
    for i in range(1, n):
        a[i] = a[i - 1] + b[i]
        cnt += a[i]

    # print(*a)
    if cnt == n**2:
        break

print(*a)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
if 2**(k)>=n**10:
    for i in range(n):
        print(n,end='')
        print(' ',end='')
else:
    for _ in range(k):
        sub=[0]*n
        for i in range(n):
            sub[max(0,i-a[i])]+=1
            if i+a[i]<n-1:
                sub[i+a[i]+1]-=1
        for i in range(1,n):
            sub[i]=sub[i]+sub[i-1]
        a=sub
    for i in sub:
        print(i,end='')
        print(' ',end='')

Submission status: Accepted

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

for i in range(k):
    now = [0]*n

    for j in range(n):
        x = li[j]
        now[max(0,j-x)] += 1
        if j+x+1 < n:
            now[j+x+1] -= 1
    
    for j in range(n-1):
        now[j+1] += now[j]

    li = now
    if min(li) >= n:
        break

print(*li)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
now = list(mapint())
from itertools import accumulate
iteration = min(N.bit_length()*4, K)
for k in range(iteration):
    nx = [0]*N
    for i, a in enumerate(now):
        nx[max(0, i-a)] += 1
        if i+a+1<N:
            nx[i+a+1] -= 1
    nx = list(accumulate(nx))
    now = nx[:]
print(*now)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import deque
import pprint

inf = 10**18
mod = 10**9+7

n,k = map(int, input().split())
b = list(map(int, input().split()))
a = [0]
for i in b:
    a.append(i)

flag = False
while k > 0 and (not flag):
    flag = True
    a2 = [0 for i in range(n+1)]
    for i,num in enumerate(a[1:]):
        l = max(i-num,0)
        r = min(i+num,n-1)
        l+=1
        r+=1
        a2[l] += 1
        if r+1 != n+1:
            a2[r+1] -= 1

    a = [0 for i in range(n+1)]
    for i in range(1, n+1):
        a[i] += a[i-1] + a2[i]
        if a[i] != n:
            flag=False
    k-=1
if flag:
    print(*[n for i in range(n)], sep=' ')
else:
    print(*a[1:], sep=' ')

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

def func(A):
    # print('start')
    # print(A)
    all_N = True
    aA = [0]*(2*N+10)
    for i, a in enu(A):
        if a != N:
            all_N = False
        st = max(0, 2*i-2*a-1)
        en = min(2*N, 2*i+2*a+1)
        aA[st] += 1
        aA[en] -= 1

    # print(aA)
    for i in range(2*N):
        aA[i+1] += aA[i]

    # print(aA)

    res = [val for i, val in enu(aA) if i%2==0]
    res = res[:N]
    # print(res)
    return res, all_N

for _ in range(K):
    A, all_N = func(A)
    if all_N:
        break
    # print(*A)

print(*A)

Submission status: Accepted

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

    for _ in range(min(K, 50)):
        B = [0] * (N + 1)
        for j in range(N):
            d = A[j]
            B[max(j - d, 0)] += 1
            B[min(j + d, N - 1) + 1] -= 1
        for i in range(N):
            B[i + 1] += B[i]
        A = B
    print(*A[:-1])


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
for _ in range(k):
    c = [0] * n
    for i in range(n):
        c[max(0, i-a[i])] += 1
        if a[i] + i + 1 < n:
            c[a[i] + i + 1] -= 1
    j = 0
    for i in range(n):
        j += c[i]
        a[i] = j

    if sum(a) == n * n:
        print(*([n] * n))
        break
else:
    print(*a)