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: Time Limit Exceeded

Solution code:
import sys
import copy
from collections import deque
stdin = sys.stdin

mod = 10**9+7

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

n, k = na()
a = na()

def calc_lux(a):
    res = [0 for _ in range(len(a))]
    for i in range(len(a)):
        light = a[i]
        for j in range(max(0, i-light), min(n-1, i+light)+1, 1):
            res[j] += 1
    return res

for _ in range(k):
    # calc lux from a
    lux = calc_lux(a)

    if a==lux:
        a = lux
        break

    # overwrite a
    a = lux
    # print(lux)

print(" ".join([str(i) for i in a]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k = map(int, input().split())
a = list(map(int, input().split()))
a = np.asarray(a, dtype=int)
for i in range(k):
    b = np.zeros(n, dtype=int)
    for j in range(n):
        if a[j]>n:
            b+=1
        if a[j]>0:
            mi = j-a[j]
            ma = j+a[j]
            if mi<0:
                mi = 0
            if ma>=n:
                ma = n-1
            for k in range(mi,ma+1):
                b[k]+=1
        else:
            b[j]+=1
    a = b
print(*a)

Submission status: Time Limit Exceeded

Solution code:
n,k=input().split(' ')
N=int(n)
K=int(k)
a = input().split(' ')
A = []
for ai in a:
  A.append(int(ai))

AA = [0] * N

for k in range(K):
  for n in range(N):
    AA[n] += 1
    if(A[n] > 0):
      for j in range(A[n]):
        if(N > n + j + 1): 
          AA[n + j + 1] += 1
        if(n >= j + 1):
          AA[n - j - 1] += 1
  for i in range(N):
    A[i] = AA[i]
    AA[i] = 0
  
pr=""
for a in A:
  pr += str(a) + " "

print(pr)

Submission status: Time Limit Exceeded

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

    max_N = [N]*N

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

        A = [i for i in illumi]

        if (A == max_N):
            print(print(" ".join(map(str, A))))
            exit(0)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K= map(int,input().split())
A = list(map(int,input().split()))
T = [0 for _ in range(N)]
for t in range(K):
    for i in range(N):
        for j in range(i-A[i],i+A[i]+1):
            if j>=0 and j<=N-1:
                T[j] += 1
    for i in range(N):
        A[i]=T[i]
        T[i]=0
A=' '.join(map(str,A))
print(A)

Submission status: Time Limit Exceeded

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

 
for _ in range(K):
  brighted = {}

  for i in range(N):  
    for j in range(max(i + 1 - A[i],1), min(i+1+A[i], N)+1):
      if j not in  brighted:
          brighted[j] = 1
      else:
          brighted[j] += 1

  for key, value in brighted.items():
    A[key-1] = value
    
  if all([m==N for m in A]):
    break
    
print(' '.join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array(lr() + [0])
# ある回数から先は全ての電球にNを足す
for _ in range(min(K, 10 ** 3)):
    next = np.array([0] * (N+1))
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    A = next.cumsum()

print(*A[:-1])

Submission status: Time Limit Exceeded

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

for i in range(K):
    tmpli = [0] * (len(A)+1)
    
    for ii in range(0, N):
        L = ii - A[ii]
        if L < 0:
            L=0

        R = ii + A[ii]
        if R > N-1:
            R=N-1

        val = 1
        tmpli[L] += val
        if R+1 != N:
            tmpli[R+1] += -val

    ruiseki = [0]*N
    ruiseki[0] = tmpli[0]
    for I in range(1, N):
        ruiseki[I] = ruiseki[I-1] + tmpli[I]
        A = ruiseki

print(*A)

Submission status: Time Limit Exceeded

Solution code:
n,k = [int(x) for x in input().split(' ')]
data = [int(x) for x in input().split(' ')]

def func1(fig,pos):
    out = [pos]
    for i in range(1, fig+1):
        if pos - i >=0:
            out.append(pos-i)
        if pos + i < n:
            out.append(pos+i)
    return out

def func2(lst):
    out = [0]*n
    for i in range(n):
        for x in func1(lst[i],i):
            out[x] += 1
    return out

for _ in range(k):
    data = func2(data)
    if min(data) == n:
        break

out = str(data[0])
for d in data[1:]:
    out += ' ' + str(d)
print(out)

Submission status: Time Limit Exceeded

Solution code:
n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
count=0
def sousa(a,k):
  B=[0]*len(a)
  for i in range(len(a)):
    for j in range(i-a[i],i+a[i]+1):
      if j>=0 and j<len(a):
        B[j]+=1
  if min(B)>=len(A):
    return B
  k-=1
  return B if k==0 else sousa(B,k)
for x in sousa(A,k):
  print(x,end=" ")

Submission status: Time Limit Exceeded

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

for i in range(K):
    B = [1] * N
    for j in range(N):
        for k in range(A[j]):
            if j-k-1 >= 0:
                B[j-k-1] += 1
            if j+k+1 <= N-1:
                B[j+k+1] += 1
    A = B
    if A == C:
        break

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k = map(int, input().split())
d = np.array(list(map(int, input().split())))
l = np.arange(n)
cnt = 0

def func(x_left, x_right):
  for i in range(n):
    temp_left = x_left[i]
    temp_right = x_right[i]
    if temp_left < 0:
      temp_left = 0
    if temp_right < 0:
      temp_right = n
    ans[temp_left:temp_right] += 1

while True:
  if cnt == k:
    break
  ans = np.array([0]*n)
  x_left = l-d
  x_right = l+d+1
  func(x_left, x_right)
  cnt += 1
  if np.all(d+n==ans):
    ans+=(k-cnt)*n
    break
  else:
    d = ans.copy()
    continue



  
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split(" "))
As = np.array(list(map(int, input().split(" "))), dtype=int)
assert len(As) == N

for k in range(K):
  count = np.zeros(N, dtype=int)
  for i, a in enumerate(As):
    # print(f"{i}を調べる")
    # print("from : ", max([0, i - a]))
    # print("from : ", min([N, i+a+1]))
    count[max([0, i - a]):min([N, i+a+1])] += 1
  As = count
print(" ".join(list(map(str, As))))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math

def changeLamp(lampList):
    newLampList = [0] * len(lampList)
    for i in range(len(lampList)):
        curLampStr = lampList[i]
        rangeLeft = math.ceil(i - curLampStr - 0.5)
        rangeLeft = rangeLeft if rangeLeft>=0 else 0
        rangeRight = int(i + curLampStr + 0.5)
        rangeRight = rangeRight if rangeRight<=len(lampList)-1 else len(lampList)-1
        for j in range(rangeLeft, rangeRight+1):
            newLampList[j] += 1

    return newLampList

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

lampList = [int(x) for x in input().split()]
for i in range(k):
    lampList = changeLamp(lampList)
    if lampList[0] == lampList[-1] and lampList[0] == len(lampList):
        break

for lamp in lampList:
    print(lamp, end=' ')

Submission status: Time Limit Exceeded

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 <= K+1:
		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: Time Limit Exceeded

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

def getmask(N,i):
  mask = list(range(i))[::-1] + list(range(N-i))[1:]
  return np.array(mask)
mask = [getmask(N+1,i) for i in range(1,N+1)]


for k in range(K):
  nextA = [np.count_nonzero(np.array(A)-i >=0) for i in mask]
  A = nextA
print(" ".join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
N, K=(int(x) for x in input().split())
A=list(map(int, input().split()))
#print(N)
#print(K)
#print(A)
for i in range(0,K):
	A_partial = [0] * N
	for j in range(0, N):
		A_min = j-A[j]
		A_max = j+A[j]
		if A_min<=0:
			A_min=0
		if A_max>=N:
			A_max=N-1
		#print(A_min,A_max)
		A_partial[A_min:A_max+1] = map(lambda x: x+1, A_partial[A_min:A_max+1])
        # newlist = map(lambda x: x*2, mylist)
		#print(A_partial)
	A = A_partial
print(*A)

Submission status: Time Limit Exceeded

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


def query(lamps):
    start_list = []
    end_list = []
    for idx, power in enumerate(lamps):
        start, end = idx - power, idx + power
        start_list.append(start)
        end_list.append(end)

    start_list.sort(reverse=True)
    end_list.sort(reverse=True)

    now = 0
    for idx in range(n):
        while start_list and start_list[-1] <= idx:
            start_list.pop()
            now += 1

        while end_list and end_list[-1] < idx:
            end_list.pop()
            now -= 1

        lamps[idx] = now


def full_check(counts, full):
    for count in counts:
        if count == full:
            continue
        else:
            return False

    return True


for _ in range(k):
    query(A)
    if full_check(A, n):
        break

print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans=np.array([0]*N)
def wa(A,ans,N):
    for n in range(N):
        haba=A[n]
        ue=n+haba
        sita=n-haba
        if sita<0:
            sita=0
        if ue>N-1:
            ue=N-1
        if haba==0:
            ans[n]+=1
        else:
            ans[sita:ue+1]+=1
    return ans
for n in range(K):
    ans=np.array([0]*N)
    if sum(ans)==N*N:
        break
    A=wa(A,ans,N)
print(' '.join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

INF = 2**31-1


class SegTree:
    def __init__(self, N):
        self.LV = (N - 1).bit_length()
        self.N0 = 2 ** self.LV
        self.data = [0] * (2 * self.N0)
        self.lazy = [0] * (2 * self.N0)

    def gindex(self, l, r):
        L = (l + self.N0) >> 1
        R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(self.LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1

    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v
            self.lazy[2*i] += v
            self.data[2*i-1] += v
            self.data[2*i] += v
            self.lazy[i-1] = 0

    def update(self, l, r, x):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        L = self.N0 + l
        R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x
                self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x
                self.data[L-1] += x
                L += 1
            L >>= 1
            R >>= 1
        for i in ids:
            self.data[i-1] = min(self.data[2*i-1], self.data[2*i])

    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l
        R = self.N0 + r

        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s


N, k = map(int, input().split())
A = list(map(int, input().split()))
T = SegTree(N)

for j in range(N):
    T.update(j, j+1, A[j])
prev_T = T

for i in range(min(k, 3*int(math.log(N))+1)):
    T = SegTree(N)
    for j in range(N):
        num = prev_T.query(j, j+1)
        T.update(max(j - num, 0), min(j + num + 1, N), 1)

    prev_T = T

ans = [0]*N
for i in range(N):
    ans[i] = prev_T.query(i, i+1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
[N, K] = list(map(int, input().split()))
A = list(map(int, input().split()))
B = [0]*N
for i in range(K):
    for j in range(N):
        for k in range(N):
            if A[k] >= abs(j-k):
                B[j] += 1
    for j in range(N):
        A[j] = B[j]
    B = [0]*N
map_result = map(str, A)
result = ' '.join(map_result)
print(result)

Submission status: Time Limit Exceeded

Solution code:
n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
count=0
def sousa(a,k):
  B=[0]*len(a)
  for i in range(len(a)):
    for j in range(i-a[i],i+a[i]+1):
      if j>=0 and j<len(a):
        B[j]+=1
  if min(B)==len(A):
    return B
  k-=1
  return B if k==0 else sousa(B,k)
for x in sousa(A,k):
  print(x,end=" ")

Submission status: Time Limit Exceeded

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

def ligh(li):
  for x in range(k):
    if li==[n]*n:
      return li
    ne=[0]*n
    ar=[]
    for (i,a) in zip(range(n),li):
      for j in range(max(0,i-a),min(i+a+1,n)):
        ne[j]+=1
    li=ne
    #print(li)
  return li

for i in ligh(a):
  print(i,end=" ")

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np

def updaetAd(Ad, index, d):
    light_range =list(i for i in range(-d+index,d+index+1,1))
    for j in light_range:
        try:
            if j >= 0:
                Ad[j] += 1
        except:
            continue


def main():
    N, K = map(int,input().split(' '))
    A = np.array(list(map(int,input().split(' '))))
    for _ in range(K):
        Ad = np.array([0] * N)
        for i in range(N):
            updaetAd(Ad, i, A[i])
        if (A == Ad).all():
            break
        A = copy.copy(Ad)

    ans = ''
    for i in A:
        ans += str(i) + ' '
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i in range(K):
  nextA = [0 for _ in range(N)]
  for j in range(N):
    lamps = [0 for _ in range(N)]
    for k in range(max(0,j-As[j]), min(j+As[j]+1, N)):
        lamps[k] = 1
    nextA = [x+y for x, y in zip(nextA, lamps)]
  As = nextA

ans = ''
for A in As:
    ans += str(A) + ' '
print(ans.strip())

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
n, k = map(int, input().split())
a = [0] + list(map(int, input().split())) + [0]
b = [0] * (n+2)
for _ in range(k):
    b = [0] * (n + 2)
    for i in range(1, n+1):
        b[max(0, i - a[i])] += 1
        b[min(n+1, i + a[i] + 1)] -= 1

    for i in range(1, n+2):
        b[i] += b[i-1]
    a = deepcopy(b)
    if all(b) == n:
        break
print(*b[1:-1])

Submission status: Time Limit Exceeded

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

for k in range(K):
    P = [0]*N
    for a in range(len(A)):
        x = int(a+1-A[a]-0.5)
        y = int(a+1+A[a]+0.5)
        if x < 0:
            x = 0
        elif y > N:
            y = N
        P[x:y] = [j+1 for j in P[x:y]]
    A = P
print(' '.join(map(str,P)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import string
import numpy as np
import math

n = list(map(int,input().split()))
b = list(map(int,input().split()))

a = np.array(b)

for i in range(n[1]):
    b = np.zeros(n[0],dtype=int)
    for j in range(n[0]):
        min = j - a[j]
        if(min<0):
            min = 0
        max = j + a[j] + 1
        if(max>n[0]):
            max = n[0]
        b[min:max] += 1
    a = b

print(*a)

Submission status: Time Limit Exceeded

Solution code:
import copy
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[copy.copy(a)]
for i in range(1,k+1):
    for j in range(n):
        mn=j-ans[i-1][j]
        mx=j+ans[i-1][j]
        if mn<0:
            mn=0
        if mx>n-1:
            mx=n-1
        ans.append([0]*n)
        for l in range(mn,mx+1):
            ans[i][l]+=1
L=[str(a) for a in ans[k]]
L=" ".join(L)
print(L)

Submission status: Time Limit Exceeded

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

    def light_range(A):
        lighted = [set() for _ in range(N)]
        for i, a in enumerate(A):
            for j in range(max(0, i-a), min(N, i+a+1)):
                lighted[j].add(i)
        return lighted
    
    lighted = light_range(A)

    def handle():
        nonlocal A, lighted
        for i, lighter in enumerate(lighted):
            A[i] = len(lighted[i])
        lighted = light_range(A)

    for _ in range(K):
        handle()
    
    print(" ".join(map(str, A)))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]

def terasu(a):
    new_a = []
    for i in range(n):
        count = 1
        for j,l in enumerate(a):
            if l > 0 and i != j:
                if abs(j-i)<=l:
                    count+=1
        new_a.append(count)
    return(new_a)

for x in range(k):
    a = terasu(a)
print(" ".join([str(x) for x in a]))

Submission status: Time Limit Exceeded

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

for cnt in range(k):
    if cnt > int(n/2):
        for l in range(n):
            a[l] += k - cnt
        break
    else:
        for i in range(n):
            abl = a[i] * 2 + 1
            for j in range(abl):
                lenge = i - a[i] + j
                if lenge >= 0 and lenge < n:
                    b[lenge] += 1
        a = b
        b = [0] * n

print(*a)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
N,P=map(int,input().split())
ans=[0 for i in range(N*3)]
A=[int(i) for i in input().split()]
for s in range(N):
    K=math.ceil(s-A[s]-0.5)
    L=math.floor(s+A[s]+0.5)
    for z in range(K+N,L+N+1):
        ans[z]+=1
P-=1
for i in range(P):
    A=[0 for i in range(N*3)]
    for s in range(N):
        K=math.ceil(s-ans[s+N]-0.5)
        L=math.floor(s+ans[s+N]+0.5)
        for z in range(K+N,L+N+1):
            A[z]+=1
    ans=copy.copy(A)
L=[str(a) for a in ans[N:2*N]]
L=' '.join(L)
print(L)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    # 愚直解
    N,K=pin()
    A=lispin()
    B=[0]*N
    B[0]=A[0]
    for j in range(1,N):
        B[j]=A[j]-A[j-1]
    #print(B)
    
    for k in range(K):
        temp=0
        C=[0]*N
        for i in range(N):
            temp+=B[i]
            #print(temp)
            if i-temp<0:

                C[0]+=1
            else:C[i-temp]+=1

            if i+temp+1<N:
                C[i+temp+1]-=1
        B=C[:]
    ans=[]
    x=0
    for c in C:
        x+=c
        ans.append(x)
    print(*ans)
#%%submit!
resolve()