Problem:


Score : 500 points

Problem Statement

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

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

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

Find the intensity of each bulb after the K operations.

Constraints

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

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

0 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

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

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

Sample Input 1

5 1
1 0 0 1 0

Sample Output 1

1 2 2 1 2 

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

Sample Input 2

5 2
1 0 0 1 0

Sample Output 2

3 3 4 4 3 



Sample input:
5 1
1 0 0 1 0


Sample output:
1 2 2 1 2

Submission status: Accepted

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

from itertools import accumulate
for i in range(min(k,100)):
  l=[0]*(n+2)
  for j in range(n):
    left=max(0,j-a[j])
    right=min(n,j+a[j])
    l[left]+=1
    l[right+1]-=1
  s=list(accumulate(l))
  # print(s)
  a=s[:n]
print(*a)

Submission status: Accepted

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

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, K, *A = map(int, read().split())

for _ in range(min(K, 42)):
    acc = [0] * (N + 1)
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N, i + a + 1)
        acc[l] += 1
        acc[r] -= 1
    acc[0] = min(N, acc[0])
    for i in range(N):
        acc[i + 1] = min(N, acc[i] + acc[i + 1])
    A = acc[:-1]
    if all(a == N for a in A):
        break
print(*A)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(min(K,100)):
    imos = [0]*(N+1)
    for i, ai in enumerate(A):
        imos[max(0, i-ai)] += 1
        imos[min(N, i+ai+1)] -= 1
    A = [imos[0]]
    for i in range(1, N):
        A += [imos[i]+A[i-1]]
print(' '.join(map(str, A)))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, K = map(int, rl().split())
    A = list(map(int, rl().split()))
    
    for _ in range(min(K, 100)):
        imos = [0] * N
        for i in range(N):
            left = max(0, i - A[i])
            right = min(N - 1, i + A[i])
            imos[left] += 1
            if right < N - 1:
                imos[right + 1] -= 1
        for i in range(1, N):
            imos[i] += imos[i - 1]
        A = imos[:]
    print(*A)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
C=[n for i in range(n)]

for m in range(k):
    B=[0 for _ in range(n)]
    for i in range(n):
        l,r=max(0,i-A[i]),min(n-1,i+A[i])
        B[l] +=1
        if r+1<n:B[r+1] -=1
    for i in range(n-1):
        B[i+1]=B[i]+B[i+1]
    A=B
    if A==C:break
print(*A)

Submission status: Accepted

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N, K = [int(a) for a in input().split()]
    A = [int(a) for a in input().split()]
    # T = int(input())
    # A = [int(a) for a in input().split()]
    # T1, T2, T3 = [int(a) for a in input().split()]

    for _ in range(K):
        AA = [0] * len(A)
        for i, ai in enumerate(A):
            l = max(0, i - ai)
            r = min(N - 1, i + ai)
            AA[l] += 1
            if r != N - 1:
                AA[r + 1] -= 1
        for i in range(len(AA) - 1):
            AA[i + 1] += AA[i]

        A = AA
        flag = True
        for a in AA:
            if a != len(A):
                flag = False
                break
        if flag:
            break
    print(' '.join([str(a) for a in A]))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

A.append(0)

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

print(*A[:-1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import time
t1=time.time()
def LI():return list(map(int,input().split()))
n,k=LI()
a=LI()

for _ in range(k):
    tab=[0]*(n)
    for i in range(n):
        q=a[i]
        if 0<=i-q:
            tab[i-q]+=1
        else:
            tab[0]+=1
        if i+q+1<=n-1:
            tab[i+q+1]-=1
        else:
            pass
    b=[tab[0]]
    for i in range(n-1):
        b.append(tab[i+1]+b[-1])
    if a==b:
        print(*a)
        exit()
    a=b[:]
    if time.time()-t1>1.5:
        print(*a)
        exit()
print(*a)

Submission status: Accepted

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):
    imosu = [0 for _ in range(len(a))]
    res = [0 for _ in range(len(a))]
    cnt = 0
    for i in range(len(a)):
        light = a[i]
        le = max(0, i-light)
        imosu[le] += 1
        if i+light < n-1:
            imosu[i+light+1] -= 1

    tmp = 0
    for i in range(len(res)):
        tmp += imosu[i]
        res[i] += tmp
    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: Accepted

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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    
    mod=10**9+7
    N,K=MI()
    A=LI()
    
    for j in range(K):
        S=[0]*(N+1)
        for i in range(N):
            l=max(0,i-A[i])
            r=min(N-1,i+A[i])
            S[l]+=1
            S[r+1]-=1
            
        temp=0
        for i in range(N):
            temp+=S[i]
            S[i+1]+=S[i]
            A[i]=S[i]
            
        if temp==N*N:
            break
        
    print(' '.join(map(str,A)))
            
        
        

        
    
    
    

main()

Submission status: Accepted

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)

N, k = map(int, input().split())
prev_arr = list(map(int, input().split()))

count = 0
for i in range(min(k, 3*int(math.log(N))+10)):
    arr = [0]*N
    for j in range(N):
        left = max(0, j-prev_arr[j])
        right = min(N-1, j+prev_arr[j])
        arr[left] += 1
        if right < N-1:
            arr[right+1] -= 1

    # print(arr)
    for j in range(1, N):
        arr[j] += arr[j-1]

    # print(arr)
    prev_arr = arr
    count += 1

# print(count)
print(*prev_arr)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def main():
    N, K = map(int, input().split())
    a = [int(i) for i in input().split()]
    A = [0] * (N + 1)
    if K >= 41:
        for i in range(1, N+1):
            if i > 1:
                print(' ', end='')
            print(N, end='')
        print()
        sys.exit()
    for i in range(1, N+1):
        A[i] = a[i - 1]
    for _ in range(K):
        count = [0] * (N + 1)
        for i in range(1, N+1):
            left_d = max(math.ceil(i - A[i]), 1)
            right_d = min(math.floor(i + A[i]), N)
            count[left_d] += 1
            if right_d + 1 <= N:
                count[right_d + 1] -= 1
        for i in range(1, N+1):
            count[i] += count[i - 1]
        A = copy.copy(count)
    
    for i in range(1, N+1):
        if i > 1:
            print(' ', end='')
        print(A[i], end='')
    print()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")
from itertools import accumulate


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

    for k in range(K):
        imos = [0]*(N+1)
        for i, a in enumerate(A):
            imos[max(i-a, 0)] += 1
            imos[min(i+a+1, N)] -= 1
        B = list(accumulate(imos))[:-1]
        if min(B) == N:
            break
        A = B
    print(" ".join(map(str, B)))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    for _ in range(min(100,K)):
        B = [0] * (N + 1)
        for i,a in enumerate(A):
            B[max(i - a,0)] += 1
            B[min(i + a + 1,N)] -= 1
        for i in range(N):
            B[i + 1] += B[i]
        A = B
    print(' '.join(map(str,A[:-1])))            
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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):
    # wia(a)
    for _ in range(k):
        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 < n-1:
                b[r+1] -= 1
        for i in range(1, n):
            b[i] += b[i-1]
        a = b
        # wia(a)
        if sum(a) == n * n:
            break
    return a


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/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[:]
        if B[0]==N and sum(B)==N:
            break
    ans=[]
    x=0
    for c in C:
        x+=c
        ans.append(x)
    print(*ans)
    #after contest
    
#%%submit!
resolve()

Submission status: Accepted

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+1)
        for aidx,a in enumerate(As):
            nAs[max(0, aidx-a)]+=1
            nAs[min(aidx+a+1,N)]-=1
        for aidx in range(1,N):
            nAs[aidx] += nAs[aidx-1]
        As = nAs[:N]
        if sum(As) == N*N:
            break
        
    print(" ".join([str(a) for a in As]))




main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from copy import deepcopy

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*(n+1)

if k > 41:
    k = 41

for _ in range(k):
    b = [0]*(n+1)
    for i,j in enumerate(a):
        b[max(0,i-j)] += 1
        b[min(n,i+j+1)] -= 1
    a = list(accumulate(b))
    for i in range(n+1):
        if a[i] >= n:
            a[i] = n

print(*a[:-1])

Submission status: Accepted

Solution code:
from copy import copy
import sys
input = sys.stdin.readline

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

    for i in range(k):
        imos = [0] * (n+1)
        for i in range(n):
            imos[max(0, i-a[i])] += 1
            imos[min(n, i+a[i]+1)] -= 1
        for i in range(n):
            imos[i+1] += imos[i]
        a = copy(imos[:-1])
        if all((a[i]==n for i in range(n))):
            break

    for i in a:
        print(i, end = ' ')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def imo(a):
    imos=[0]*(n+1)

    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,i+a[i]+1)]-=1
    
    immo=[0]*(n+1)
    immo[0]=imos[0]
    for i in range(n):
        immo[i+1]=immo[i]+imos[i+1]

    return immo[:n]

for i in range(min(k,41)):
    a=imo(a)
    
print(*a)

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,k=map(int, readline().rstrip().split())
    arr=list(map(int, readline().rstrip().split()))
    for _ in range(k):
        tmp=[0]*n
        for i in range(n):
            x = i - arr[i]
            y = i + arr[i] + 1
            if x<0:
                x=0
            if y<n:
                tmp[y]-=1
            tmp[x]+=1
        sm=tmp[0]
        arr[0]=tmp[0]
        for i in range(1,n):
            arr[i]=arr[i-1]+tmp[i]
            sm+=abs(tmp[i])
        if tmp[0]==n and sm==n:
            break
    print(" ".join(map(str,arr)))
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

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

cur = A[:]
for k in range(K):
    imos = [0] * (N+1)
    for i in range(N):
        imos[max(i-cur[i], 0)] += 1
        imos[min(i+cur[i]+1, N)] -= 1
    imos = list(accumulate(imos))
    cur = imos[:-1]
    if min(cur) == N:
        break
print(*cur)

Submission status: Accepted

Solution code:
def im(a):
    imos = [0] * (3*N+1)
    for i in range(N):
        imos[N+i-min(N,a[i])] += 1
        imos[N+i+min(N,a[i])+1] -= 1
    cs = [0]
    for i in range(1,2*N+1):
        cs.append(cs[i-1]+imos[i-1])
    return cs[N+1:]

N,K,*A = map(int, open(0).read().split())
for i in range(K):
    A = im(A)
    if A.count(N) == N:
        break
print(*A)

Submission status: Accepted

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

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
from itertools import accumulate
for i in range(k):
    temp = [0]*(n + 1)
    for j in range(n):
        b = a[j]
        left = max(0, j - b)
        right = min(n - 1, j + b)
        temp[left] += 1
        temp[right + 1] -= 1
    a = list(accumulate(temp))[:n]
    if min(a) == n:
        print(*a)
        sys.exit()
print(*a)

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
while K > 0 and not all(a == N for a in A):
    imos = [0] * (N + 1)
    for i, a in enumerate(A):
        imos[max(0, i - a)] += 1
        imos[min(N, i + a + 1)] -= 1
    A = list(accumulate(imos))[:-1]
    K -= 1
print(*A)

Submission status: Accepted

Solution code:
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    n, k = ZZ()
    A = ZZ()+[0]

    for _ in range(k):
        if all([A[i] >= n for i in range(n)]): break
        nA = [0] * (n+1)
        for i in range(n):
            nA[max(0, i-A[i])] += 1
            nA[min(n, i+1+A[i])] -= 1
        for i in range(1, n+1): nA[i] += nA[i-1]
        A = nA
    print(*A[:-1])

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def S(): return sys.stdin.readline().rstrip()

N,K = map(int,S().split())
A = LI()

from itertools import accumulate

ANS = A+[0]

for i in range(K):
    B = [0]*(N+1)
    for j in range(N):
        B[max(0,j-ANS[j])] += 1
        B[min(N,j+ANS[j]+1)] -= 1
    ANS = list(accumulate(B))
    for i in range(N):
        if ANS[i] != N:
            break
    else:
        break

del ANS[N]
print(*ANS)

Submission status: Accepted

Solution code:
import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(K):
    newA = [0]*N
    for j in range(N):
        newA[max(0,j-A[j])] += 1
        if j+A[j]+1 < N:
            newA[min(N-1,j+A[j]+1)] -= 1
    A = list(itertools.accumulate(newA))
    if A == [N]*N:
        break
print(*A)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(min(K,41)):
    imos = [0]*(N+1)
    for i, ai in enumerate(A):
        imos[max(0, i-ai)] += 1
        imos[min(N, i+ai+1)] -= 1
    A = [imos[0]]
    for i in range(1, N):
        A += [imos[i]+A[i-1]]
print(' '.join(map(str, A)))

Submission status: Accepted

Solution code:
import numpy as np
 
N, K = map(int, input().split(' '))
A = tuple(map(int, input().split(' ')))
indexes = np.arange(0, N)
 
dp = np.zeros(shape=N + 1, dtype=np.int64)
 
for k in range(K):
    np.add.at(dp, np.maximum(0, indexes - A), 1)
    np.add.at(dp, np.minimum(N, indexes + A + 1), -1)
    A = dp.cumsum()[:-1]
    if np.all(A == N):
        break
    dp *= 0
 
print(' '.join(map(str, A)))

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(K):
        m = True
        a = [0] * N
        t = 0
        for i in range(N):
            t += a[i] + 1
            if i + A[i] + 1< N:
                a[i + A[i] + 1] -= 1
            a[i] = t
        t = 0
        b = [0] * N
        for i in reversed(range(N)):
            t += b[i]
            b[i] = t
            t += 1
            if i - A[i] - 1 >= 0:
                b[i - A[i] - 1] -= 1
            A[i] = a[i] + b[i]
            if A[i] < N:
                m = False
        if m:
            break
    return A

print(*main())

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
event = []
for i in range(k):
    data = [0 for _ in range(n + 1)]
    for i in range(n):
        data[max(0,i-a[i])] += 1
        data[min(n,i+a[i]+1)] -= 1

    for i in range(n):
        data[i+1] += data[i]
    check = True
    for i in range(n):
        if data[i] != n:
            check = False
            break
    if check:
        print(*data[:n])
        exit()
    a = data
print(*a[:n])

Submission status: Accepted

Solution code:
N, K, *A = map(int, open(0).read().split())

x = A[:]

for _ in range(min(50, K)):
    y = [0] * (N + 1)
    for i in range(N):
        y[max(0, i - x[i])] += 1
        y[min(N, i + x[i] + 1)] -= 1
        
    for i in range(N):
        y[i + 1] += y[i]
        
    x = y[:]
        
    
print(*x[:-1])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

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


for p in range(k):
    b = [0]*n
    for i in range(n):
        k = i+a[i]+1
        w = i-a[i]
        if k < n:
            b[k] -= 1
        if 0 <= w:
            b[w] += 1
        else:
            b[0] += 1

    for j in range(1,n):
        b[j] = b[j]+b[j-1]
    a = b
    if sum(a) == s:
        break

print(*a)

Submission status: Accepted

Solution code:
from itertools import accumulate

def mi():
    return map(int, input().split())

def main():
    N, K = mi()
    A = list(mi())

    for _ in range(K):
        l = [0]*N
        for i in range(N):
            left = max(i-A[i], 0)
            right = min(i+A[i]+1, N)
            l[left] += 1
            if right < N:
                l[right] -= 1
        if A != list(accumulate(l)):
            A = list(accumulate(l))
        else:
            break
    print(' '.join(list(map(str, A))))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for k in range(K):
    next_array = [1] * N
    minus_array = [0] * N
    plus = 0
    for i in range(N):
        next_array[i] += plus
        plus += 1
        if i + A_array[i] < N:
            minus_array[(i + A_array[i])] += 1
        plus -= minus_array[i]

    minus_array = [0] * N
    plus = 0
    for i in range(N - 1, -1, -1):
        next_array[i] += plus
        plus += 1
        if i - A_array[i] >= 0:
            minus_array[(i - A_array[i])] += 1
        plus -= minus_array[i]
    A_array = copy.deepcopy(next_array)
    if A_array == [N] * N:
        break

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

Submission status: Accepted

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

pre = A
for i in range(0,K,1):
    now = [0]*N

    kuiL = [0]*N
    kuiR = [0]*N
    for j in range(0,N,1):
        #for k in range(max(0,j-pre[j]),min(N,j+pre[j]+1),1):
        #    now[k]+=1
        kuiL[max(0,j-pre[j])]+=1
        kuiR[min(N-1,j+pre[j])]+=1
    tmp = 0
    for j in range(0,N,1):
        if j!=0:
            tmp = tmp + kuiL[j]-kuiR[j-1]
        else:
            tmp = tmp + kuiL[j]
        now[j]+=tmp

    owari = True
    for j in range(0,N,1):
        if now[j]!=N:
            owari = False
        pre[j]=now[j]
    if owari:
        break
print(" ".join(list(map(str,now))))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import time
t1=time.time()
def LI():return list(map(int,input().split()))
n,k=LI()
a=LI()

for _ in range(k):
    tab=[0]*(n)
    for i in range(n):
        q=a[i]
        if 0<=i-q:
            tab[i-q]+=1
        else:
            tab[0]+=1
        if i+q+1<=n-1:
            tab[i+q+1]-=1
        else:
            pass
    b=[tab[0]]
    for i in range(n-1):
        b.append(tab[i+1]+b[-1])
    a=b[:]
    if time.time()-t1>1.5:
        print(*a)
        exit()
print(*a)

Submission status: Accepted

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

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

    if 70 <= K:
        ans = [N] * N
        print(" ".join(map(str, ans)))
    else:
        for _ in range(K):
            B = [0] * (N + 1)
            for i in range(N):
                head = max(i - A[i], 0)
                tail = min(i + A[i] + 1, N)
                B[head] += 1
                B[tail] -= 1
            A = list(accumulate(B))[:N]
        print(" ".join(map(str, A)))
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from copy import copy, deepcopy
from collections import Counter
from math import sqrt, floor, factorial, log
from itertools import permutations, combinations, combinations_with_replacement
from operator import mul
from functools import reduce
import bisect

MOD = 10**9 + 7
INF = float('inf')

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

#A = [0 for i in range(N)]
B = [0 for i in range(N)]

# print(A)
for _ in range(K):
    B = [0 for i in range(N)]
    for i in range(N):
        B[max(i-A[i], 0)] += 1
        idx = min(i+A[i]+1, N)
        if idx != N:
            B[idx] -= 1
    # print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    # print(B)
    A = B.copy()
    if _ > 10 * int(log(N)):
        break

L = " ".join([str(x) for x in A])
print(L)

Submission status: Accepted

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


class RAQ():
    
    def __init__(self, size):
        """初期化"""
        self.size = size
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [0] * treesize
        self.st = st
        self.offset = len(st) // 2

    @classmethod
    def from_array(cls, a):
        st = cls(len(a))
        for i, x in enumerate(a):
            st.add(i, i+1, x)
        return st

    def _add_topdown(self, a, b, value, k=1, l=0, r=-1):
        """区間[a, b) に対する加算
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        if r == -1:
            r = self.offset
        if r <= a or b <= l:
            return
        if l == r - 1:
            self.st[k] += value
            return
        if a <= l and r <= b:
            self.st[k] += value
            return
        mid = (l + r) // 2
        self._add(a, b, value, k * 2, l, mid)
        self._add(a, b, value, k * 2 + 1, mid, r)

    def _add_bottomup(self, a, b, value):
        """区間[a, b) に対する加算
        """
        a += self.offset
        b += self.offset - 1
        while a < b:
            if a & 1:
                self.st[a] += value
                a += 1
            a >>= 1
            if not b & 1:
                self.st[b] += value
                b -= 1
            b >>= 1
        if a == b:
            self.st[a] += value

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        return self._add_bottomup(a, b, value)

    def get(self, key):
        """値の取得"""
        offset = len(self.st) // 2
        k = offset + key
        v = self.st[k]
        k >>= 1
        while k > 0:
            v += self.st[k]
            k >>= 1
        return v


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A):
    KL = N.bit_length() * 2 + 4
    if K > KL:
        print(*([N] * N))
        return
    raq = RAQ.from_array(A)
    a = [0 for i in range(N)]

    for k in range(min(K, KL)):
        for i in range(N):
            a[i] = raq.get(i)
            raq.add(i, i+1, -a[i])
        for i in range(N):
            l = max(0, i-a[i])
            r = min(N, i+1+a[i])
            raq.add(l, r, 1)
    print(*[raq.get(i) for i in range(N)])


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))