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:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(k):
    list = [1 for _ in range(n)]
    for i, d in enumerate(a):
        if d == 0:
            continue
        for j in range(-d, d+1):
            if j == 0:
                continue
            if i+j >= 0:
                try:
                    list[i+j] += 1
                    # print(i, j)
                except:
                    pass
    a = list.copy()
for i in range(n-1):
    print(a[i], end=" ")
print(a[-1])

Submission status: Time Limit Exceeded

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))


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

B = [0] * N
for _ in range(K):
    for i in range(N):
        d = i - A[i]
        count = 0
        while True:
            if d < 0:
                count += 1
                d += 1
                continue
            if d > N-1:
                break
            if count == A[i] * 2 + 1:
                break

            B[d] += 1
            d += 1
            count += 1
    A = B
    B = [0] * N

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

Submission status: Time Limit Exceeded

Solution code:
import copy
n,k,*A = map(int,open(0).read().split())

for _ in range(k):
    C = [0] * n
    for i,d in enumerate(A):
        for j in range(i-d,i+d+1):
            if 0<=j<n:
                C[j] += 1
    A = copy.deepcopy(C)

    up = True
    for c in C:
        if c != n:
            up = False          
    if up:
        break

print(*C)

Submission status: Time Limit Exceeded

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

l_chk=[0] * N
cnt = 0
for i in range(K):

    for j in range(N):
        cnt = 0
        for k in range(N):
            if j == k:
                cnt = cnt + 1
            elif abs(k-j) <= A[k]:
                cnt = cnt + 1
        l_chk[j] = cnt

    for j in range(N):
        A[j] = l_chk[j]


print(*A)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

new_a = [0 for i in range(n)]
for i in range(k):
    for j in range(n):
        for k in range(j-a[j],j+a[j]+1):
            if k < 0 or n <= k:
                continue
            else:
                new_a[k] += 1
    a = copy.copy(new_a)
    new_a = [0 for i in range(n)]

print(" ".join(list(map(str, a))))

Submission status: Time Limit Exceeded

Solution code:
import sys


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n, k = _ia()
    a = list(_ia())
    for _ in range(k):
        ap = [0] * n
        for i, ai in enumerate(a):
            for j in range(max(0, i-ai), min(n, i+ai+1)):
                ap[j] += 1
        a = ap

    return " ".join(map(str, a))


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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for j in range(k):
  b = [0]*n
  for i in range(n):
    for e in range(max(0, i-a[i]), min(n, i+a[i]+1)):
      b[e] += 1
  a = b
  if a.count(n) == n:
    break
print(" ".join(list(map(str, a))))

Submission status: Time Limit Exceeded

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s + '\n')
def wi(n): sys.stdout.write(str(n) + '\n')
def wia(a): sys.stdout.write(' '.join([str(x) for x in a]) + '\n')


def solve(n, k, a):
    ch = set([i for i in range(n)])
    for _ in range(k):
        if len(ch) == 0:
            break
        b = [0] * n
        ii = list(ch)
        for i in ii:
            cnt = 0
            for j in range(n):
                if j - a[j] - 0.5 < i < j + a[j] + 0.5:
                    cnt += 1
            b[i] = cnt
            if b[i] == n:
                ch.remove(i)
        a = b
    return a


def main():
    n, k = ria()
    a = ria()
    wia(solve(n, k, a))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
for i in range(K):
  if a == [N]*N:
    break
  temp = [0]*N
  for j in range(N):
    m = max(0,j-a[j])
    M = min(N-1,j+a[j])
    #print(j,m,M)
    for k in range(m,M+1):
      temp[k] += 1
  a = temp
b=[str(i) for i in a]
b=" ".join(b)
print(b)

Submission status: Time Limit Exceeded

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

for i in range(k):
    if 2**i>=n:
        ans = [n]*n
        break
    ans = [0]*n
    for j in range(n):
        ans[max(j-a[j],0)] += 1
        if j+a[j]+1 < n:
            ans[j+a[j]+1] -= 1
    for j in range(1,n):
        ans[j] += ans[j-1]
    
    a = ans
    
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()

Submission status: Time Limit Exceeded

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

for i in range(k):
  b=[0]*n
  if min(a)>=n:
    for j in range(n):
      a[j]+=k-i      
  for j in range(n):
    for m in range(j-a[j],j+a[j]+1):
      if 0<=m<=n-1:
        b[m]=b[m]+1
  a=b
for i in a:
  print(i,end=' ')

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(K):
    B = [1]*N
    for i in range(N):
        for j in range(1, A[i]+1):
            if i-j >= 0:
                B[i-j] += 1
            if i+j < N:
                B[i+j] += 1
    A = B

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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(k):
    new_a = [0 for _ in range(n)]
    for i in range(n):
        tera = a[i]
        if i-tera < 0:
            left = 0
        else:
            left = i-tera
        if i+tera >=n:
            right = n-1
        else:
            right = i+tera
        for j in range(left, right+1):
            new_a[j]+= 1
    a = new_a
print(*a)

Submission status: Time Limit Exceeded

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

cnt = [0 for _ in range(n)]
for i in range(n):
    if a[i]:
        l = max(0, i-a[i])
        r = min(n-1, i+a[i])

        cnt[l] += 1
        if r < n-1: cnt[r+1] -= 1

for i in range(1, n): cnt[i] += cnt[i-1]
for i in range(n):
    if a[i]: cnt[i] -= 1

for i in range(n): a[i] = cnt[i]+1

k -= 1

while k:
    cnt = [0 for _ in range(n)]
    for i in range(n):
        if a[i]:
            l = max(0, i-a[i])
            r = min(n-1, i+a[i])

            cnt[l] += 1
            if r < n-1: cnt[r+1] -= 1

    for i in range(1, n): cnt[i] += cnt[i-1]

    for i in range(n):
        if a[i]: cnt[i] -= 1

    f = False

    for i in range(n):
        a[i] = cnt[i] + 1

        if a[i] < n: f = True


    if not f: break

    k -= 1

print(" ".join(list(map(str, a))))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
List = list(map(int, input().split()))
strength = [1]*N
for k in range (K):
  for i in range(N):
    for j in range(N):
      if i==j:
        pass
      else:
        if j-List[j]-0.5 < i < List[j]+j+0.5:
          strength[i] += 1
        else:
          pass
      #print(List,strength)
  List = strength
  strength = [1]*N
print(*List)

Submission status: Time Limit Exceeded

Solution code:
l=list(map(int, input().split(' ')))
n=l[0]
k=l[1]
l=list(map(int, input().split(' ')))
buckets = n*[0]
i=0
while i<k:
    i+=1
    j=0
    while j<n:
        thing=l[j]
        for a in range(int(j-thing+0.5), int(j+thing+1.5)):
            if a>=0 and a<=n-1:
                buckets[a]+=1
        j+=1
    j=0
    while j<n:
        l[j]=buckets[j]
        buckets[j]=0
        j+=1
for i in l:
    print(i, end=' ')

Submission status: Time Limit Exceeded

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

dp = [[0]*N for _ in range(K+1)]
for i in range(N):
    dp[0][i] = S[i]

for i in range(K):
    for j in range(N):
        m = max(0, j-dp[i][j])
        M = min(N, j+dp[i][j]+1)
        for k in range(m, M):
            dp[i+1][k] += 1
ans = ""
for i in range(N):
    ans += str(dp[K][i]) + " "
print(ans[:-1])

Submission status: Time Limit Exceeded

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

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

    A = copy.deepcopy(illumi)

    k += 1

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

Submission status: Time Limit Exceeded

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

for i in range(k):
    akarusanext=[0]*n
    for j in range(n):
        kagen=max(j-akarusa[j],0)
        jogen=min(j+akarusa[j],n-1)
        for k in range(kagen,jogen+1):
            akarusanext[k]+=1
    akarusa=akarusanext

for i in range(n):
    print(akarusa[i], end=" ")

Submission status: Time Limit Exceeded

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

for _ in range(K):
    lights = np.zeros(N, dtype='int32')
    for i, flash in enumerate(A):
        front = i-flash if i-flash >= 0 else 0
        back = i+flash if i+ flash < N else N-1
        lights[front:back+1] += 1
    A = np.copy(lights)

for i in A:
    print(int(i),end=' ')
print()

Submission status: Time Limit Exceeded

Solution code:
import copy
n,k,*A = map(int,open(0).read().split())

for _ in range(k):
    C = [0] * n
    for i,d in enumerate(A):
        for j in range(i-d,i+d+1):
            if 0<=j<n:
                C[j] += 1
    A = copy.deepcopy(C)

print(*C)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    for _ in [0] * k:
        new_A = np.array([0] * n)
        for i in range(n):
            left = i - A[i]
            right = i + A[i] + 1
            if left < 0:
                if right >= n:
                    new_A += 1
                else:
                    new_A[:right] += 1

            else:
                if right >= n:
                    new_A[left:] += 1
                else:
                    new_A[left:right] += 1


        A = new_A
        if min(A) == n:
            break

    for a in A:
        print(a, end=" ")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#c
n,k=map(int, input().split())
a = list(map(int, input().split()))
import numpy as np
a_n = np.array(a)
for i in range(k):
    result = np.array([0]*n, dtype=object)
    for j in range(n):
        count = 0
        for l in range(n):
            if l > j:
                if l-a_n[l]-0.5<j:
                    count += 1
            elif l < j:
                if l+a_n[l]+0.5>j:
                    count += 1
            else:
                count += 1
        result[j] =count
    a_n = result
ans=[str(a) for a in a_n]
ans=" ".join(ans)
print(ans)

Submission status: Time Limit Exceeded

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

A=list(map(int,input().split()))
A=[0]+A

def get_new(old):
    new = [0 for i in range(N+1)]
    for i in range(1,N+1):
        for j in range(max(1,i-old[i]),min(N,i+old[i])+1):
            new[j]+=1
    return new

for step in range(K):
    if (step % 2 == 0):
        B = get_new(A)
    else:
        A = get_new(B)

if (step % 2 == 0):
    print(" ".join(map(str, B[1:])))
else:
    print(" ".join(map(str, A[1:])))

Submission status: Time Limit Exceeded

Solution code:
import copy

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

B = [0] * N

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
sys.setrecursionlimit(int(pow(10,6)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


# @lru_cache(None)
n,k=l()
A=l()
# print(*A)
while(k>0):
    pref=[0 for i in range(n+2)]
    Aprev=A[::]
    for i in range(n):
        # print(*pref)
        l=i-A[i]+1
        r=i+1+A[i]
        pref[max(1,l)]+=1
        pref[min(n+1,r+1)]-=1

    for i in range(1,n+1):
        pref[i]+=pref[i-1]
    A=pref[1:n+1]
    if(A==Aprev):
        break
    # print(*A)
    k-=1

print(*A)

Submission status: Time Limit Exceeded

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

aa = map(int, input().split())

old = aa

for _ in range(k):
    new = [0] * n
    for i, a in enumerate(old):
        low = max(0, i-a)
        hi = min(n-1, i+a)+1
        for j in range(low, hi):
            new[j] += 1
    old = new

new = list(map(str, new))

print(' '.join(new))

Submission status: Time Limit Exceeded

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


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, k = input_to_int_map()
    a_array = input_to_int_tuple()

    ret = [_ for _ in a_array]
    for i in range(k):
        temp_ret = [0] * n
        for j, a in enumerate(ret):
            for k in range(max(0, j - a), min(n, j + a + 1)):
                temp_ret[k] += 1
        ret = temp_ret

    return " ".join(map(str, ret))


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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p = [int(i) for i in input().split()]
for _ in range(k):
    t = [1] * n
    for i, j in enumerate(p):
        for l in range(1, j + 1):
            if i - l >= 0:
                t[i - l] += 1
            if i + l <= n - 1:
                t[i + l] += 1
    p = t
    if sum(p) == n ** 2:
        break
print(*p)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
for _ in range(K):
  ls=[0 for _ in range(N)]
  for i in range(N):
    for j in range(max([0,i-A[i]]),min([N,i+A[i]+1])):
      ls[j]+=1
  A=ls.copy()
print(" ".join(map(str,A)))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()

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

        if A.count(N) == N:
            break

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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]
print(*a)

Submission status: Time Limit Exceeded

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


for k in range(K):
    illumi = [0] * N
    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 = copy.deepcopy(illumi)

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

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


def light(As,N):
    A0 = np.array([0] * N)
    for i in range(N):
        lp = As[i]
        lmin = max(0, i - lp)
        lmax = min(N - 1, i + lp)
        A0[lmin:lmax + 1] += 1
    return A0

for i in range(K):
    As = light(As, N)

print(*As,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
class DualSegTree():
    def __init__(self,n):
        self.n=n
        self.data=[0]*n*2
    def propagate(self,i):
        if i>=self.n*2:return
        data=self.data
        c,j=0,i
        while j:
            j>>=1
            c+=1
        for j in range(c-1,0,-1):
            j=i>>j
            data[j+j]+=data[j]
            data[j-~j]+=data[j]
            data[j]=0
    def update(self,l,r,x):
        data=self.data
        l+=self.n
        r+=self.n
        self.propagate(l)
        self.propagate(r)
        while l<r:
            if l&1:
                data[l]+=x
                l+=1
            if r&1:
                r-=1
                data[r]+=x
            l>>=1
            r>>=1
    def get(self,i):
        i+=self.n
        self.propagate(i)
        return self.data[i]
def main():
    n,k,*a=map(int,open(0).read().split())
    seg=DualSegTree(n)
    seg.data[n:]=a
    for _ in range(k):
        d=DualSegTree(n)
        get,update=seg.get,d.update
        m=10**18
        for i in range(n):
            t=get(i)
            if t<m:m=t
            update(max(0,i-t),min(i-~t,n),1)
        seg=d
        if m>n:break
    print(' '.join(str(seg.get(i))for i in range(n)))
main()

Submission status: Time Limit Exceeded

Solution code:
n,k = 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(k-j):
        b[j] += 1
  a = b  
  b = [0]*n
  
print(*a)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
sys.setrecursionlimit(int(pow(10,6)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


# @lru_cache(None)
n,k=l()
A=l()

while(k>0):
    pref=[0 for i in range(n+2)]
    for i in range(n):
        # print(*pref)
        l=i-A[i]+1
        r=i+1+A[i]
        pref[max(1,l)]+=1
        pref[min(n+1,r+1)]-=1

    for i in range(1,n+1):
        pref[i]+=pref[i-1]
    A=pref[1:n+1]
    k-=1

print(*A)

Submission status: Time Limit Exceeded

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()
    anss = [0]*n
    while k != 0:
        flag = 0
        anss = [0]*n
        for i in range(n):
            ai = a[i]
            if ai >= n-1:
                flag += 1
            for j in range(max(0,i-ai), min(n,i+ai+1)):
                anss[j] += 1
        if flag == n:
            for i in range(n):
                anss[i] = n
            break
        a = copy.copy(anss)
        k -= 1
    print(' '.join(list(map(str,anss))))
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, k = nm()
    if k > 45:
        k = 45
    a = nl()
    b = [0]*n
    for _ in range(k):
        for i in range(n):
            b[max(0, i - a[i])] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        for i in range(n-1):
            b[i+1] += b[i]
            a[i] = 0
        a[-1] = 0
        b, a = a, b
    print(*a)
    return

solve()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
for q in range(K):
    foo = [1 for k in range(3*N+1)]
    for k in range(N):
        for j in range(1, A[k]+1):
            foo[k-j+N] +=1
            foo[k+j+N] +=1
    #print(foo)

    for k in range(N):
        A[k] = foo[k+N]
    #print(A)

ans = ""
for k in range(len(A)):
    ans += str(A[k]) + " "

print(ans.rstrip())

Submission status: Time Limit Exceeded

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

counts = [0]*N

for i in range(K):
    for j, a in enumerate(A):
        for k in range(max(0, j-a), min(j+a+1, N)):
            counts[k] += 1
    A = counts
    counts = [0]*N
print(" ".join(map(str, A)))

Submission status: Time Limit Exceeded

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

for i in range(k):
    if 2**i>=n:
        ans = [n]*n
        break
    ans = [0]*n
    for j in range(n):
        ans[max(j-a[j],0)] += 1
        if j+a[j]+1 < n:
            ans[j+a[j]+1] -= 1
    for j in range(1,n):
        ans[j] += ans[j-1]
    
    a = ans[:]
    
print(*ans)

Submission status: Time Limit Exceeded

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():
    # 区間加算、上書き、一点取得
    class SegmentTree:
        def __init__(self, n, ele, segfun):
            #####単位元######要設定0or1orinf
            self.ide_ele = ele
            self.segfun = segfun
            ####################
            self.n = n
            self.N0 = 1 << n.bit_length()
            self.data = [self.ide_ele] * (self.N0 * 2)
        def ref(self):
            self.data = [self.ide_ele] * (self.N0 * 2)
            return

        def update_add(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] += val
                    l += 1
                if r & 1:
                    self.data[r - 1] += val
                    r -= 1
                l //= 2
                r //= 2

        def update(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] = self.segfun(self.data[l], val)
                    l += 1
                if r & 1:
                    self.data[r - 1] = self.segfun(self.data[r - 1], val)
                    r -= 1
                l //= 2
                r //= 2

        def query(self, i):
            i += len(self.data) // 2
            ret = self.data[i]
            while i > 0:
                i //= 2
                ret = self.segfun(ret, self.data[i])
            return ret
    N, K = LI()
    A = LI()
    S = SegmentTree(N+1,0,lambda a, b: a+b)
    for i in range(N):
        S.update(i,i+1,A[i])
    #for i in range(N):
    #    print(S.query(i))
    for _ in range(min(60,K)):
        cur = N
        L = []
        R = []
        for i in range(N):
            a = S.query(i)
            L.append(max(0,i-a))
            R.append(min(N,i+a+1))
            if cur>a:
                cur = a
        if cur==N:
            break
        S.ref()
        for l,r in zip(L,R):
            S.update_add(l,r,1)
        #for i in range(N):
        #    print(S.query(i))
        #input()
    ans = [S.query(i) for i in range(N)]
    print(" ".join(map(str,ans)))
    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: Time Limit Exceeded

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

for i in range(k):
  for j in range(n):
    for r in range(j-a[j], j+a[j]+1):
      if(0<=r and r<n):
        b[r] += 1
  a = b[:]
  b = [0 for _ in range(n)]
  
ans = ""
for i in range(n):
  ans += str(a[i]) + " "
print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N,K = isRaw()
    As = isRaw()
    for k in range(K):
        nAs = [0]*N
        for aidx,a in enumerate(As):
            for x in range(max(0,aidx-a),min(aidx+a+1,N)):
                nAs[x]+=1
        As = nAs
        if sum(As) == N*N:
            break
        
    print(" ".join([str(a) for a in As]))




main()

Submission status: Time Limit Exceeded

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

for _ in range(K):
    A = [sum(y - A[y] - 0.5 < x < y + A[y] + 0.5 for y in range(N)) for x in range(N)]

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