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())
List = list(map(int, input().split()))
data_x = [0]*N
res = [0]*N

def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  return data

def ruiseki_f(y, k):
  ruiseki = [0]*k
  ruiseki[0] = y[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + y[i+1]
  return ruiseki

for i in range(K):
  Flag = True
  data_x = imosu(List,N)
  List = ruiseki_f(data_x,N)
  for j in range(N):
    if not List[j] == N:
      Flag = False
  if Flag:
    break
res = List
print(*res)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
List = list(map(int, input().split()))
data_x = [0]*N
res = [0]*N

def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  return data

def ruiseki_f(y, k):
  ruiseki = [0]*k
  ruiseki[0] = y[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + y[i+1]
  return ruiseki

for i in range(K):
  data_x = imosu(List,N)
  List = ruiseki_f(data_x,N)
  for j in range(N):
    Flag = True
    if not List[j] == N:
      Flag = False
  if Flag:
    break
res = List
print(*res)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
List = list(map(int, input().split()))
data_x = [0]*N
res = [0]*N

def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  return data

def ruiseki_f(y, k):
  ruiseki = [0]*k
  ruiseki[0] = y[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + y[i+1]
  return ruiseki

for i in range(K):
  data_x = imosu(List,N)
  List = ruiseki_f(data_x,N)
  for j in range(N):
    if List[j] == N:
      break
res = List
print(*res)

Submission status: Time Limit Exceeded

Solution code:
buf = list(map(int, input().split()))
N=buf[0]
K=buf[1]
A = list(map(int, input().split()))
 
if K<N/2:
  for k in range(K):
    B=[0]*len(A)
    for a in range(0,len(A)):
      for i in range(a-A[a],a+A[a]+1):
        if i>=0 and i<=len(A)-1:
          B[i]=B[i]+1
    A=B
else:
    A=[N]*len(A)  
print(" ".join([str(a) for a in A]))

Submission status: Time Limit Exceeded

Solution code:
buf = list(map(int, input().split()))
N=buf[0]
K=buf[1]
A = list(map(int, input().split()))
 
if K<N:
  for k in range(K):
    B=[0]*len(A)
    for a in range(0,len(A)):
      for i in range(a-A[a],a+A[a]+1):
        if i>=0 and i<=len(A)-1:
          B[i]=B[i]+1
    A=B
else:
    A=[N]*len(A)  
print(" ".join([str(a) for a in A]))

Submission status: Time Limit Exceeded

Solution code:
buf = list(map(int, input().split()))
N=buf[0]
K=buf[1]
A = list(map(int, input().split()))

if K<N:
  for k in range(K):
    B=[0]*len(A)
    for a in range(0,len(A)):
      for i in range(a-A[a],a+A[a]+1):
        if i>=0 and i<=len(A)-1:
          B[i]=B[i]+1
    A=B
else:
    A=[N]*len(A)  
print(" ".join([str(a) for a in A]))

Submission status: Time Limit Exceeded

Solution code:
buf = list(map(int, input().split()))
N=buf[0]
K=buf[1]
A = list(map(int, input().split()))

for k in range(K):
  B=[0]*len(A)
  for a in range(0,len(A)):
    for i in range(a-A[a],a+A[a]+1):
      if i>=0 and i<=len(A)-1:
        B[i]=B[i]+1
  A=B
print(" ".join([str(a) for a in A]))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
imos = [0]*(N+1)

# 全体でO(NlogN) ≒ 10^6
for k in range(K): # 下のifによってO(logN)で抑えられる.
    if min(A) == N:
        break

    imos = [0]*(N+1)
    for i,a in enumerate(A): # O(N)
        imos[max(0, i-a)] += 1
        imos[min(N, i + a + 1)] -= 1
        
    A = [imos[0]]
    for i in range(1,len(imos)-1): # O(N)
        A.append(A[i - 1] + imos[i])
        
print(*A, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit


@njit
def get_a(n, a):
    b = np.zeros((n + 1), dtype=np.int64)
    for i in range(n):
        ai = a[i]
        l = max(0, i - ai)
        r = min(n, i + ai + 1)
        b[l] += 1
        b[r] -= 1
    return np.cumsum(b)[:n]


if __name__ == '__main__':
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A = np.array(A, dtype=np.int64)
    for _ in range(K):
        A = get_a(N, A)
    print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit


@njit
def get_a(n, a):
    b = np.zeros((n + 1), dtype=np.int64)
    for i in range(n):
        l = max(0, i - a[i])
        r = min(n - 1, i + a[i])
        b[l] += 1
        if r + 1 < n:
            b[r + 1] -= 1

    return np.cumsum(b)[:n]


if __name__ == '__main__':
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A = np.array(A, dtype=np.int64)
    for _ in range(K):
        A = get_a(N, A)
    print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit


@njit
def get_a(n, a):
    b = np.zeros((n + 1), dtype=np.int64)
    for i in range(n):
        l = max(0, i - a[i])
        r = min(n - 1, i + a[i])
        b[l] += 1
        if r + 1 < n:
            b[r + 1] -= 1

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

    return b[:-1]


if __name__ == '__main__':
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A = np.array(A)
    for _ in range(K):
        A = get_a(N, A)
    print(*A)

Submission status: Time Limit Exceeded

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

for _ in range(k):
    bl = [ 0 for _ in range(n) ]

    for i in range(n):
        left = max(0, i-al[i])
        right = min(n-1, i+al[i])
        bl[left] += 1
        if (right+1) < n:
            bl[right+1] -= 1
    
    for i in range(1, n):
        bl[i] += bl[i-1]
    al = bl

for v in bl:
    print(v, end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int, input().split())
a=list(map(int, input().split()))
from itertools import accumulate
for _ in range(min(50,k)):
    new=[0]*n
    for i in range(n):
        j=a[i]
        l=max(0,i-j)
        r=min(n-1,i+j)
        new[l]+=1
        if r+1<n:
            new[r+1]-=1
    new=list(accumulate(new))
    a=new
print(*a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def imos(n,k,a):
    
    l=np.zeros((n+1),dtype=np.int64)
    for i in range(n):
        ai=a[i]
        start=max(0,i-ai) #StartIndex
        end=min(n,i+ai+1) #EndIndex + 1
        l[start]+=1
        l[end]-=1
    return np.cumsum(l)[:n]

if __name__=="__main__":
    n,k=map(int, input().split())
    a=list(map(int, input().split()))
    for _ in range(k):
        a=imos(n,k,a)
        if a.min()==n:
            break   
    
    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(1,min(K+1,42)):
    B = [0]*N
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1,i+A[i])
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
            
    for i in range(1,N):
        B[i] += B[i-1]
    A = B
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(1,min(K+1,50)):
    B = [0]*N
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1,i+A[i])
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
            
    for i in range(1,N):
        B[i] += B[i-1]
    A = B
print(*A)

Submission status: Time Limit Exceeded

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

    def move(lst):
        tmp = [0] * (N + 1)
        for i in range(N):
            a = lst[i]
            left = max(0, i - a)
            right = min(N, i + a + 1)
            tmp[left] += 1
            tmp[right] -= 1
        for i in range(N):
            tmp[i + 1] += tmp[i]
        for i in range(N):
            if lst[i] != N:
                return tmp
        print (*tmp[:-1])
        exit()

    for _ in range(K):
        A = move(A)
    print (*A[:-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    def check(lst):
        for i in range(N):
            if lst[i] != N:
                return False
        return True

    def move(lst):
        tmp = [0] * (N + 1)
        for i in range(N):
            a = lst[i]
            left = max(0, i - a)
            right = min(N, i + a + 1)
            tmp[left] += 1
            tmp[right] -= 1
        for i in range(N):
            tmp[i + 1] += tmp[i]
        return tmp

    for i in range(K):
        A = move(A)
        if check(A):
            # print (i)
            break

    print (*A[:-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def check(lst):
    for i in range(N):
        if lst[i] != N:
            return False
    return True

def move(lst):
    tmp = [0] * (N + 1)
    for i in range(N):
        a = lst[i]
        left = max(0, i - a)
        right = min(N, i + a + 1)
        tmp[left] += 1
        tmp[right] -= 1
    for i in range(N):
        tmp[i + 1] += tmp[i]
    return tmp

for i in range(K):
    A = move(A)
    if check(A):
        # print (i)
        break

print (*A[:-1])

Submission status: Time Limit Exceeded

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

def check(lst):
    # print (set(lst))
    if (N == lst[0]) and (len(set(lst[:-1])) == 1):
        return True
    else:
        return False

def move(lst):
    tmp = [0] * (N + 1)
    for i in range(N):
        a = lst[i]
        left = max(0, i - a)
        right = min(N, i + a + 1)
        tmp[left] += 1
        tmp[right] -= 1
    for i in range(N):
        tmp[i + 1] += tmp[i]
    return tmp

for i in range(K):
    A = move(A)
    if check(A):
        # print (i)
        break

print (*A[:-1])

Submission status: Time Limit Exceeded

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

def check(lst):
    if (N == lst[0]) and (len(set(lst)) == 1):
        return True
    else:
        return False

def move(lst):
    tmp = [0] * (N + 1)
    for i in range(N):
        a = lst[i]
        left = max(0, i - a)
        right = min(N, i + a + 1)
        tmp[left] += 1
        tmp[right] -= 1
    for i in range(N):
        tmp[i + 1] += tmp[i]
    return tmp

for _ in range(K):
    A = move(A)
    if check(A):
        break

print (*A[:-1])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
li = list(map(int,input().split()))
ans = [0]*(n+1)
tmp = [0]*(n+1)
tmp_sum = []
#print(ans)
#[0, 0, 0, 0, 0]

for kkk in range(k):
    #print(li,'li')
    for i,l in enumerate(li):
        if l != 0:
            start = max(0,i-l)
            end = min(n,i+l+1)
            #print(start,'start',end,'end')
            tmp[start] += 1
            #print(end,len(tmp),'aaa')
            tmp[end] -= 1
    #print(tmp,'tmp')
    last = 0
    for t in tmp:
        last = t+last
        tmp_sum.append(last)
    for i,l in enumerate(li):
        if l == 0:
            tmp_sum[i] += 1
    ans = tmp_sum[:n]
    li = tmp_sum[:n]
    tmp = [0]*(n+1)
    tmp_sum = []
    #if len(set(ans)) == 1:
    #    break
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
from itertools import accumulate
import numpy as np
def main():
  n,k=map(int,input().split())
  a=np.array(list(map(int,input().split())))
  k=k if k<50 else 50
  for _ in range(k):
    b=np.zeros(n+1,dtype=int)
    for i in range(n):
      ai=a[i]
      l,r=i-ai,i+ai+1
      l=0 if l<0 else l
      r=n if r>n else r
      b[l]+=1
      b[r]-=1
    b=tuple(accumulate(b))[:-1]
    a=b
    if min(set(b))==n:
      break
  print(*a)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import numpy as np
  n,k=map(int,input().split())
  a=np.array(list(map(int,input().split())))
  k=k if k<50 else 50
  for _ in range(k):
    b=np.zeros(n+1,dtype=int)
    for i in range(n):
      ai=a[i]
      l=0 if i-ai<0 else i-ai
      r=n if i+ai+1>n else i+ai+1
      b[l]+=1
      b[r]-=1
    for i in range(n-1):
      b[i+1]+=b[i]
    a=b[:-1]
    if min(a)==n:
      break
  print(*a)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
# C - Lamps

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

b = [0] * n
for kk in range(k):
    l = [i - a[i] for i in range(n)]
    r = [i + a[i] for i in range(n)]
    l.sort()
    r.sort()
    ln = 0
    rn = 0
    for i in range(n):
        while ln < n and l[ln] <= i:
            ln += 1
        while rn < n and r[rn] <  i:
            rn += 1
        b[i] = ln - rn
    a, b = b, a
    if all(v >= n for v in a):
        break

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict as dd
from collections import deque as dq
import itertools as it
from math import sqrt, log, log2
from fractions import Fraction

n, k = map(int, input().split())
intensity = list(map(int, stdin.readline().split()))

count = 0
while count < k:
    totsum = 0
    prefs = [0]*n
    zeros = []
    for i in range(n):
        l = i - intensity[i]
        r = i + intensity[i] + 1

        prefs[max(l, 0)] += 1
        if r <= n-1: 
            prefs[r] += -1
            
    for i in range(1, n):
        prefs[i] += prefs[i-1]
        totsum += prefs[i]
    
    if totsum == n*n:
        print(*prefs)
        exit()
    
    intensity = prefs
    count += 1

print(*prefs)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict as dd
from collections import deque as dq
import itertools as it
from math import sqrt, log, log2
from fractions import Fraction

n, k = map(int, input().split())
intensity = list(map(int, stdin.readline().split()))

count = 0
while count < k:
    totsum = 0
    prefs = [0]*n
    zeros = []
    for i in range(n):
        if intensity[i]!=0:
            l = i - intensity[i]
            r = i + intensity[i] + 1

            prefs[max(l, 0)] += 1
            if r <= n-1: 
                prefs[r] += -1
        else:
            zeros.append(i)
            
    for i in range(1, n):
        prefs[i] += prefs[i-1]
        totsum += prefs[i]
    
    for i in zeros:
        if intensity[i] == 0:
            prefs[i] += 1
            totsum += 1
    
    if sum(prefs) == n*k:
        print(*prefs)
        exit()
    
    intensity = prefs
    count += 1

print(*prefs)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict as dd
from collections import deque as dq
import itertools as it
from math import sqrt, log, log2
from fractions import Fraction

n, k = map(int, input().split())
intensity = list(map(int, stdin.readline().split()))

count = 0
while count < k:
    totsum = 0
    prefs = [0]*n
    zeros = []
    for i in range(n):
        if intensity[i]!=0:
            l = i - intensity[i]
            r = i + intensity[i] + 1

            prefs[max(l, 0)] += 1
            if r <= n-1: 
                prefs[r] += -1
        else:
            zeros.append(i)
            
    for i in range(1, n):
        prefs[i] += prefs[i-1]
        totsum += prefs[i]
    
    for i in zeros:
        if intensity[i] == 0:
            prefs[i] += 1
            totsum += 1
    
    if totsum == n*n:
        print(*prefs)
        exit()
    
    intensity = prefs
    count += 1

print(*prefs)

Submission status: Time Limit Exceeded

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

@njit(cache=True)
def foo(N, K, A):
    for i in range(K):
        AA = [0] * N
        for j in range(len(A)):
            p = A[j]
            st = max(0, j - p)
            ed = min(N - 1, j + p)
            for k in range(st, ed+1):
                AA[k] += 1
        A = AA[:]
    return A
A = foo(N, K, A)
print(' '.join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, sys.stdin.readline().rstrip().split())
an = list(map(int, sys.stdin.readline().rstrip().split()))

import numpy as np

t= min(k, 45)

for _ in range(t):
    bn = [0]*n
    for i in range(n):
        bn[max(i - an[i], 0)] += 1

        if i+ an[i]+1 <n:
            bn[i+an[i]+1] -=1
    an = np.cumsum(bn)


print(*an)

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, sys.stdin.readline().rstrip().split())
an = list(map(int, sys.stdin.readline().rstrip().split()))

import numpy as np

t= min(k, 45)
bn = np.zeros((t,n), dtype=int)

for i in range(t):

    for j in range(n):
        bn[i][max(j - an[j], 0)] += 1

        if j+ an[j]+1 <n:
            bn[i][j+an[j]+1] -=1
    an = np.cumsum(bn[i])


print(*an)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = [*map(int, input().split())]
for i in range(k):
    B = [0]*(n+1)
    for j in range(n):
        l = max(0, j - A[j])
        r = min(n, j + A[j] + 1)
        B[l] += 1; B[r] -= 1
    for j in range(n-1): B[j+1] += B[j]
    B.pop()
    if A == B: break
    A = B
print(*A, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = [*map(int, input().split())]
for i in range(k):
    B = [0]*n
    for j in range(n):
        l = max(0, j-A[j])
        r = j + A[j] + 1
        B[l] += 1
        if r <= n-1: B[r] -= 1
    is_same = True
    for j in range(n-1):
        B[j+1] = B[j+1] + B[j]
        if B[j+1] != n: is_same = False
    if is_same: break
    A = B
print(*B,sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, sys.stdin.readline().rstrip().split())
an = list(map(int, sys.stdin.readline().rstrip().split()))

import numpy as np

t= min(k, 45)

for i in range(t):
    bn = [0]*n
    for i in range(n):
        bn[max(i - an[i], 0)] += 1

        if i+ an[i]+1 <n:
            bn[i+an[i]+1] -=1
    an = np.cumsum(bn)

#an = [int(i) for i in an]
print(*an)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
A=[*map(int,input().split())]
# print(n,k)
# print(A)
# B = []
m = min({19,k,n})
# B = [[0]*n for _ in range(m+1)]
# B[0] = A
# print('m',m)
# print(B)
for i in range(m):

    # print(i,B)
    B = [0]*n

    for j in range(n):
        d = A[j] # 強さ
        l = max(0, j-d) # 範囲
        r = j+d+1 # 範囲
        # print('j,d,l,r',j,d,l,r)
        B[l] += 1
        if r <= n-1: B[r] -= 1

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

# print('---')
# print(B)
# for i in range(n-1):
#     B[i+1] = B[i+1] + B[i]
# print(B)
print(*B,sep=' ')
# print(A)
# print(*A, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
A=[*map(int,input().split())]
# print(n,k)
# print(A)
B = []
for i in range(min({18,k,n})):
    # print(i,A)
    B = [0]*n
    for j in range(n):
        d = A[j] # 強さ
        l = max(0, j-d) # 範囲
        r = min(n-1, j+d) # 範囲
        # print('j,d,l,r',j,d,l,r)
        for k in range(l,r+1): # [l,r]
            B[k] += 1
    A = B

print(*A, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

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

    # 実験 n=100 k=100 l=[0]*100 で回すとi=13で全部行き渡るようになった
    # f=False
    # for a in range(n):
    #   if l[a]<n-1:
    #     f=True
    # if not f:
    #   return i

    ff=True
    for j in range(n):
      left=j-l[j]
      if left<0:
        left=0
      else:
        ff=False
      nxtl[left]+=1

      right=j+l[j]+1
      if right<n:
        nxtl[right]-=1
        ff=False

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

    if ff:
      return ' '.join(str(x) for x in l)

    l=nxtl

    # print(l)

  return ' '.join(str(x) for x in l)

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    memo = [0] * (n + 1)
    for _ in range(k):
        for i, aa in enumerate(a):
            bf = (i - aa if i - aa >= 0 else 0)
            af = (i + aa + 1 if i + aa < n else n)
            memo[bf] += 1
            memo[af] -= 1
        for i in range(n):
            memo[i + 1] += memo[i]
            a[i] = memo[i]
            memo[i] = 0
        if set(a) == {n}:
            break
    print(*a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A, dtype=int)


fin = [N] * N

def calc_b(a):
    b = np.zeros(N, dtype=np.int64)
    for i, _a in enumerate(a):
        l = max(0, i - _a)
        r = min(N - 1, i + _a)

        # imos hou
        b[l] += 1
        if r + 1 < N:
            b[r + 1] -= 1

    b = np.cumsum(b)
    # print('b_sum', b)
    return b


for k in range(min(K,100)):
    # print('a', a)
    a = calc_b(a)
    if all(a == fin):
        break

a = [str(_) for _ in a]
print(' '.join(a))
# print('step=', k)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)
    
    from itertools import accumulate

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    check = [n] * n
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        a = list(accumulate(memo))[:-1]
        if a == check:
            break
    print(*a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A, dtype=int)


fin = [N] * N

def calc_b(a):
    b = np.zeros(N, dtype=np.int64)
    for i, _a in enumerate(a):
        l = max(0, i - _a)
        r = min(N - 1, i + _a)

        # imos hou
        b[l] += 1
        if r + 1 < N:
            b[r + 1] -= 1

    b = np.cumsum(b)
    # print('b_sum', b)
    return b


for k in range(K):
    # print('a', a)
    a = calc_b(a)
    if all(a == fin):
        break

a = [str(_) for _ in a]
print(' '.join(a))
# print('step=', k)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
R = [N]*N
def update(A):
    b = [0]*N
 
    for i,a in enumerate(A):
        l = max(0,i-a)
        r = min(N-1,i+a)
 
        b[l] += 1
        if r+1 < N:
            b[r+1] -= 1
    
    res = []
    s = 0
    for i in b:
        s += i
        res.append(s)
    return res
 
for _ in range(K):
    A = update(A)
    if A == R:
      break
print(*A)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        for j in range(n):
            memo[j + 1] += memo[j]
        a = memo[:-1]
        if set(a) == {n}:
            break
    print(*a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        for j in range(n):
            memo[j + 1] += memo[j]
        a = memo[:-1]
        if set(a) == n:
            break
    print(*a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from itertools import accumulate

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        a = list(accumulate(memo))[:-1]
        if set(a[:-1]) == n:
            break
    print(*a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

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

for ii in range(min(50,k)):
	if ii == 0:
		ans = [0]*n
		for i in range(n):
			if arr[i] == 0:
				ans[i] = 1
			else:
				ans[i] = arr[i]
	else:
		ans = [0]*n
	for x in range(n):
		for ll in range(x-arr[x],x+arr[x]+1):
			if 0<=ll<=n-1:
				if x==ll:continue
				ans[ll] += 1
	if ii!=0 :ans = [i+1 for i in ans]
	#print("ans : ",ans)
	arr = ans[:]
	if ii > (2*10**5)//2:
		break
print(*arr)

Submission status: Time Limit Exceeded

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))

Submission status: Time Limit Exceeded

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

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

    cnt2 = 0
    for j in range(N):
        if A[j] == N:
            cnt2 += 1
    if cnt2 == N:
        break
    #print(lis)
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):
    b = [0] * (n + 1)
    for i in range(n):
        b[max(0, i - a[i])] += 1
        b[min(n, i + a[i] + 1)] -= 1
    a[0] = b[0]
    for i in range(1, n):
        a[i] = b[i] + a[i - 1]
    if sum(a) == pow(n, 2):
        break
print(*a)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = [int(x) for x in input().strip().split()]
    l = [0] * (N + 1)
    for i, a in enumerate(A):
        l[max(0, i-a)] += 1
        l[min(N, i+a+1)] -= 1
    p = 0
    cumsum = [0] * (N + 1)
    for i in range(N+1):
        p += l[i]
        cumsum[i] = p
    cumsum_ = A + [0]
    for k in range(min(K-1, 50)):
        p = 0
        for i in range(N+1):
            l[max(0, i-cumsum[i])] += 1
            l[min(N, i+cumsum[i]+1)] -= 1
            l[max(0, i-cumsum_[i])] -= 1
            l[min(N, i+cumsum_[i]+1)] += 1

        cumsum_ = cumsum[:]
        for i in range(N+1):
            p += l[i]
            cumsum[i] = p

    print(*cumsum[:-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = [int(x) for x in input().strip().split()]
    l = [0] * (N + 1)
    for i, a in enumerate(A):
        l[max(0, i-a)] += 1
        l[min(N, i+a+1)] -= 1
    p = 0
    cumsum = [0] * (N + 1)
    for i in range(N+1):
        p += l[i]
        cumsum[i] = p
    cumsum_ = A + [0]
    for k in range(min(K-1, 100)):
        p = 0
        for i in range(N+1):
            l[max(0, i-cumsum[i])] += 1
            l[min(N, i+cumsum[i]+1)] -= 1
            l[max(0, i-cumsum_[i])] -= 1
            l[min(N, i+cumsum_[i]+1)] += 1

        cumsum_ = cumsum[:]
        for i in range(N+1):
            p += l[i]
            cumsum[i] = p

    print(*cumsum[:-1])

if __name__ == '__main__':
    main()