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:
import sys

def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    key = 30
    nn = n
    while nn > 0:
        key += 1
        nn //= 2
    
    for _ in range(min([key, k])):
        b = [0]*n
        for i in range(n):
            l, r = max([i-a[i], 0]), min([i+a[i], n-1])
            b[l] += 1
            if r != n-1:
                b[r+1] -= 1
        for i in range(n):
            a[i] = 0
            a[i] += b[i]
            if i != 0:
                 a[i] += a[i-1]
    print(*a)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    n,k = map(int,input().split())
    a = list(map(int, input().split()))
    ans = [0 for _ in range(n+1)]
    for _ in range(k):
        ans = [0 for _ in range(n+1)]
        for i in range(n):
            [l,r] = [max(0,i-a[i]),min(n-1,i+a[i])]
            ans[l] += 1
            ans[r+1] -= 1
        for i in range(n):
            ans[i+1] += ans[i]
        a = ans
        if ans[0] >= n and ans[n-1] >= n:
            print(*[n for _ in range(n)])
            return
    x = []
    for i in range(n):
        x.append(ans[i])
    print(*x)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))
#print("k=",0,":",*lst1)
for i in range(k):
    res = [0]*(n+2)
    for j in range(n):
        l = max(-1,j - lst1[j])
        r = min(n,j + lst1[j] + 1)
        res[l+1] += 1
        res[r+1] -= 1
    for j in range(1,n+1):
        res[j] += res[j-1]
    lst1 = res[1:n+1]
    if lst1[0] == lst1[-1] == n:
        break
    #print("k=",i+1,":",*lst1)

print(*lst1)

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

# N = k = 200000
# prev_arr = [0]*N

count = 0
for i in range(min(k, 3*int(math.log(N))+5)):
    que = []
    arr = [0]*N
    for j in range(N):
        heapq.heappush(que, j+prev_arr[j])
        while que[0] < j:
            heapq.heappop(que)
        arr[j] += len(que)
    # print(arr)

    que = []
    for j in reversed(range(N)):
        heapq.heappush(que, -(j-prev_arr[j]))
        while -que[0] > j:
            heapq.heappop(que)
        arr[j] += len(que) - 1

    prev_arr = arr
    count += 1

# print(count)
print(*prev_arr)

Submission status: Accepted

Solution code:
def update(a, n):
    ret = [0] * (n+1)
    for i in range(n):
        l = max(0, i - a[i])
        r = min(i + a[i] + 1, n)
        ret[l] += 1
        ret[r] -= 1
    data = [0] * (n+1)
    data[0] = ret[0]
    for i in range(1, n+1):
        data[i] = data[i-1] + ret[i]
    return data[:-1]


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

k = min(k, 120)

for i in range(k):
    ret = update(ret, n)

print(' '.join(list(map(str, ret))))

Submission status: Accepted

Solution code:
from collections import deque

n,k=map(int,input().split())
A=list(map(int,input().split()))
for i in range(min(k,50)):
    P=[]
    M=[]
    cnt=0
    for a in range(n):
        if A[a]==n:
            cnt+=1
            continue
        P.append(a-A[a])
        M.append(a+A[a]+1)
    P.sort()
    M.sort()
    P=deque(P)
    M=deque(M)
    C=[]
    m=n
    for j in range(n):
        if P:
            while P[0]<=j:
                P.popleft()
                cnt+=1
                if not P:
                    break
        if M:
            while M[0]<=j:
                M.popleft()
                cnt-=1
                if not M:
                    break
        C.append(cnt)
        m=min(cnt,m)
    A=C
    if m==n:
        break
print(*A)

Submission status: Accepted

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, K = LI()
A = LI()


def main():
    ans = A.copy()
    w = [0] * (N + 1)
    for i in range(N):
        w[max(0, i - A[i])] += 1
        w[min(N, i + A[i] + 1)] -= 1
    
    for _ in range(K):
        x = 0
        l = [0] * (N + 1)
        flag = True
        for i in range(N):
            x += w[i]
            if x != N:
                flag = False
            ans[i] = x
            l[max(0, i - x)] += 1
            l[min(N, i + x + 1)] -= 1
        if flag:
            break
        w = l
    
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(K):
  R = [ {} for j in range(N)]

  for j in range(N):
    s = A[j]
    # j - s ~ j + s
    if min(j+s, N-1) in R[max(0, j-s)]:
      R[max(0, j-s)][min(j+s, N-1)] += 1
    else:
      R[max(0, j-s)][min(j+s, N-1)] = 1
        
  # Make Next List
  #print(R)
  L = [0 for j in range(N)]
  t = 0
  for j in range(N):
    r = R[j]
    for k, v in r.items():
      t += v
      L[k] += v
    A[j] = t
    t -= L[j]
    
  if A[0] == N and A[-1] == N:
    for j in range(N):
      if A[j] < N:
        break
    else:
      break
print(*A)

Submission status: Accepted

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

    for _ in range(min(K,50)):
        e_list_1 = [0] * N
        l_1 = [0] * N
        v = 0
        for i,a in enumerate(A_list):
            l_1[i] = v 
            e_list_1[min(i + a, N-1)] += 1
            v = v + 1 - e_list_1[i]
        
        e_list_2 = [0] * N
        v = 0
        for _i,a in enumerate(A_list[::-1]):
            i = N-1-_i
            A_list[i] = l_1[i] + v + 1
            e_list_2[max(i-a, 0)] += 1
            v = v + 1 - e_list_2[i]
        
    print(*A_list)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import itertools
gcd = math.gcd
n,k = ma()
A = list(ma())
def imos(ls,st,ed):
    n = len(ls) -2
    for i in range(n):
        if 0< st[i]:
            ls[st[i]] += 1
        else:
            ls[0] +=1
        if ed[i] <=n:
            ls[ed[i]+1] -=1
        else:
            ls[n+1] -=1
    for i in range(n+1):
        ls[i+1] += ls[i]
low = []
high = []
ls = [0]*(n+2)
for i in range(n):
    a = A[i]
    low.append(i+1-a)
    high.append(i+1+a)
for i in range(k):
    imos(ls,low,high)
    if ls[1:-1] == [n]*n:
        break
    #print(ls[1:-1])
    if i==k-1:break
    for j in range(n):
        a = ls[j+1]
        low[j] = j+1-a
        high[j] = (j+1+a)
    ls = [0]*(n+2)
print(*ls[1:-1])

Submission status: Accepted

Solution code:
from decimal import *
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())



def solve(N, K, A):
    def update():
        new_A = [0]*N
        end_idx = [0]*N
        num_act = 0
        num_max = 0
        for i in range(N):
            end_idx[min(i+A[i], N-1)]+=1
            num_act+=1
            new_A[i] = num_act
            num_act-=end_idx[i]
        end_idx = [0]*N
        num_act = 0
        num_max = 0
        for i in range(N-1, -1, -1):
            tmp = A[i]
            new_A[i]+= num_act
            if new_A[i] == N:
                num_max+=1
            if A[i]>0:
                num_act += 1
                end_idx[max(0,i-tmp)]+=1
            num_act -= end_idx[i]
        return new_A, num_max
    for _ in range(K):
        A, num_max = update()
        if num_max == N:
            return [str(n) for n in A]
    return [str(n) for n in A]
    



N, K = rrm()
A = rrm()
ans = solve(N, K, A)
print(' '.join(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))
n,k = l_in()
A = l_in()


t = 0
while t < k:
    left = [0]*n
    right = [0]*n

    
    for i, a in enumerate(A):
        left[max(i-a,0)] += 1
        right[min(i+a,n-1)] += 1

    flag = True
    A = [0]*n
    current = 0
    for i in range(n):
        current += left[i]
        A[i] = current
        flag = flag and A[i] == n
        current -= right[i]

    t += 1

    if flag:
        break

    

print(*A)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))
import math
    
N, K = mi()
A = li()
 
#light = [0] * (N+2)
#A = [0] + A + [0]
#print(math.log(N, 2))
'''
thre = 0
for i in range(N):
    if A[i] < i:
        thre = max(thre, i-A[i])
'''
if K > pow(N, 0.5) + 1:
        for i in range(N):
            print(N, '', end='')
        print()
        exit()
 
 
for i in range(K):
    new = [0] * (N+1)
    for j in range(N):
        new[max(j-A[j], 0)] += 1
        new[min(j+A[j]+1, N)] += -1
        #print(new)
    new = list(accumulate(new))
    A = new[:N]
 
for i in range(N):
    print(A[i], '', end='')
print()

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
r=range(n)
while k:
 k-=1;b=[0]*n*3
 for i in r:t=a[i];b[max(0,i-t)]+=1;b[i-~t]-=1
 for i in r:b[i+1]+=b[i]
 a=b[:n]
 if min(a)==n:break
print(*a)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
r=range(n)
while k:
 k-=1;b=[0]*-~n
 for i in r:t=a[i];b[max(0,i-t)]+=1;b[min(n,i-~t)]-=1
 for i in r:b[i+1]+=b[i]
 a=b[:n]
 if min(a)==n:break
print(*a)

Submission status: Accepted

Solution code:
import sys
def main(N, K, A):
    for k in range(min(50, K)):
        C = [0] * (N + 1)
        for i in range(N):
            a = A[i]
            C[max(0, i - a)] += 1
            C[min(N, i + a + 1)] -= 1
        A[0] = C[0]
        for i in range(1, N):
            A[i] = A[i - 1] + C[i]
    return A

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(int, input().split())
    print(*main(N, K, A))

Submission status: Accepted

Solution code:
import sys
import itertools

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    
    K = min(50, K)
    for i in range(K):
        B = [0]*N
        for j in range(N):
            st = max(0, j - A[j])
            ed = j + A[j] + 1
            B[st] += 1
            if ed < N:
                B[ed] -= 1
        Bcum = itertools.accumulate(B)
        A = list(Bcum)
    print(*A)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy
import bisect
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
    for i in range(n-1):
        b[i+1] += b[i]
    b.pop()
    a = deepcopy(b)
    
    if bisect.bisect_left(a, n) == 0: break
    
print(*a)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def dd(al,n):
	imos=[0]*(n+1)
	for i, v in enumerate(al):
		imos[max(0, i-v)]+=1
		imos[min(n, i+v+1)]-=1
	ret = [0]*(n)
	ret[0]=imos[0]
	mmm=0
	for i, v in enumerate(imos[1:-1],1):
		ret[i]=ret[i-1]+imos[i]
	return ret, min(ret)



def main():
	#a = int(input())
	n, k = tin()
	#s = input()
	al=lin()
	for _ in range(k):
		nal, min_al = dd(al,n)
		if min_al == n:
			print(*nal)
			return
		al=nal
	print(*nal)
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys

def input():
    return sys.stdin.readline().strip()

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

    for _ in range(K):
        data = [0] * len(A)
        for i in range(N):
            range_mai = i - A[i]
            range_pura = i + A[i]
            if range_mai < 0:
                range_mai = 0
            if range_pura > N - 1:
                range_pura = N - 1
            data[range_mai] += 1
            if range_pura + 1 != N:
                data[range_pura + 1] -= 1

        A = list(accumulate(data))
        if min(A) == N:
            break
    print(*A)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
n,k=mi()
a=li()
for i in range(k):
    tmp=[0]*n
    for j in range(n):
        x1=max(0,j-a[j])
        x2=min(n+1,j+a[j])
        tmp[x1]+=1
        if(x2<n-1):
            tmp[x2+1]-=1
       
    f=1
    a[0]=tmp[0]
    if(a[0]<n):
        f=0
    for j in range(1,n):
        tmp[j]+=tmp[j-1]
        a[j]=tmp[j]
        if(a[j]<n):
            f=0
    if(f):
        break
print(*a)

Submission status: Accepted

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


def calc_imos(arr):
    imos = [0] * (N + 1)
    for i, a in enumerate(arr):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        imos[l] += 1
        imos[r + 1] -= 1
    imos = list(accumulate(imos))
    return imos[:-1]


for k in range(min(50, K)):
    A = calc_imos(A)
print(*A, sep=' ')

Submission status: Accepted

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

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

    ans = [0]*N
    A[0] = tmp[0]
    for i in range(1, N):
        A[i] = A[i-1] + tmp[i]

    # print(*A)
    if sum(A) == N*N:
        break
print(*A)

Submission status: Accepted

Solution code:
import itertools

n,k= map(int, input().split())
a= list(map(int, input().split()))
if k>=50:
    ans=[n]*n
    print(*ans)
    exit()

ans=[0]*(n+1)
# ims
for i in range(k):
    ansx=[0]*(n+1)
    for j in range(n):
        if i==0:
            ansx[max(j - a[j], 0)] += 1
            ansx[min(n, j + a[j] + 1)] -= 1
        else:
            ansx[max(j - ans[j], 0)] += 1
            ansx[min(n, j + ans[j] + 1)] -= 1

    ansx = list(itertools.accumulate(ansx))
    ans=ansx


print(*ans[:n])

Submission status: Accepted

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

for k in range(K):
    delta = [0]*(N+1)
    for i,val in enumerate(res):
        left = max(0, i-val)
        right = min(N, i+val+1)
        delta[left] += 1
        delta[right] -= 1
    res = [0]*N
    res[0] = delta[0]
    for i in range(N-1):
        res[i+1] = res[i]+delta[i+1]
    if delta[0] == -delta[N] == N:
        break

print(*res)

Submission status: Accepted

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

try_count = min(50, k)

for i in range(try_count):
    imos_up = [0 for _ in range(len(a))]
    imos_down = [0 for _ in range(len(a))]
    for j in range(len(a)):
        up = max(0,j-a[j])
        imos_up[up] += 1
        down = min(len(a)-1, j+a[j])
        imos_down[down] += 1
    now = 0
    for j in range(len(a)):
        now += imos_up[j]
        a[j] = now
        now -= imos_down[j]

print(" ".join(list(str(s) for s in a)))

Submission status: Accepted

Solution code:
from random import randint
n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(k):
    cur = 0
    new_a = [-1]*n
    end = [0]*n
    for j in range(n):
        cur += 1
        new_a[j] += cur
        end[min(j+a[j],n-1)] += 1
        cur -= end[j]
    end = [0]*n
    for j in range(n)[::-1]:
        cur += 1
        new_a[j] += cur
        end[max(j-a[j],0)] += 1
        cur -= end[j]
    a = new_a
    if a[0] == n:
        print(*[n]*n)
        exit()
print(*a)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
ex=0
for test in range(K):
    ex+=1
    D=[0 for i in range(N+1)]
    for i in range(N):
        D[max(0,i-A[i])]+=1
        D[min(N,i+A[i]+1)]-=1
    A[0]=D[0]
    for i in range(1,N):
        A[i]=A[i-1]+D[i]
    if set(A)=={N}:
        break
print(*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:
import itertools

N, K = map(int,input().split())
A = list(map(int,input().split()))
B = [0] * (N+1)
chk = [N] *N
for k in range(K):
    if A == chk:
        break
    for i in range(N):
        if A[i] == 0:
            B[i] += 1
            B[i+1] -= 1
            continue
        l = i - A[i]
        r = i + A[i]
        if l <= 0:
            B[0] += 1
        else:
            B[l] += 1
        if r >= N-1:
            B[N] -= 1
        else:
            B[r+1] -= 1        
    A = list(itertools.accumulate(B))[:-1]
    B = [0] * (N+1)
print(*A)
#print("B = " ,B)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,K = map(int,input().split())
a = list(map(int,input().split()))

for k in range(K):
    light = [0]*n
    st = [0]*n
    skip = True
    for i in range(n):
        if i - a[i] >= 0:
            light[i-a[i]] += 1
        else:
            light[0] += 1
        
        if i + a[i] + 1 <= n-1:
            light[i + a[i] + 1] -= 1

    st[0] = light[0]
    if st[0] < n-1:
        skip = False
    for i in range(1,n):
        st[i] = st[i-1] + light[i]
        if st[i] < min(n-1-i,i):
            skip = False
    
    if skip:
        if k < K-1:
            for _ in range(n):
                print(n,end =" ")
            exit()
        else:
            for ans in st:
                print(ans, end = " ")
            exit()
    a = st[::]
for ans in a:
    print(ans, end = " ")

Submission status: Accepted

Solution code:
import sys
import heapq
import random
import collections

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(k,lst):  # fix inputs here
    console("----- solving ------")

    arr = [0 for _ in lst]
    for _ in range(min(k,50)):
        uppp = [0 for _ in range(len(lst)+1)]
        down = [0 for _ in range(len(lst)+1)]
        for i,x in enumerate(lst):
            uppp[max(0,i - x)] += 1
            down[min(len(lst),i + x + 1)] += 1
        # console("ud")
        # console(uppp)
        # console(down)
        cur = 0
        for i,x in enumerate(arr):
            cur += uppp[i]
            cur -= down[i]
            arr[i] = cur
        # console("ar")
        # console(arr)
        # console()
        lst = arr

    return " ".join([str(x) for x in lst])


def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return


# for case_num in range(int(input())):
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
_,k = list(map(int,input().split()))
lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    # grid = []
    # for _ in range(nrows):
    #     grid.append(list(map(int,input().split())))

res = solve(k,lst)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
print(res)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    cur = A
    for _ in range(K):
        prev = cur
        cur = [0] * N
        pls = [0] * (N+1)
        for i in range(N):
            l = max(i - prev[i], 0)
            r = min(i + prev[i], N-1)
            pls[l] += 1
            pls[r+1] -= 1
        num = 0
        for i in range(N):
            num += pls[i]
            cur[i] = num
        same = True
        for i in range(N):
            if cur[i] != prev[i]:
                same = False
                break
        if same:
            break
    print(*cur)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

if K >= 40:
    print(' '.join(map(str, [N]*N)))
    exit()

for _ in range(K):
    events = [[] for _ in range(N*2+2)]
    for i, a in enumerate(As):
        l = 2*(i-a)-1
        r = 2*(i+a)+1
        events[-1 if l < -1 else l].append(i)
        events[N*2 if r > N*2 else r].append(i)
    active = [0] * N
    L = 0
    nextAs = [0] * N
    for i in range(N):
        for k in events[2*i-1]:
            if active[k]:
                active[k] = 0
                L -= 1
            else:
                active[k] = 1
                L += 1
        nextAs[i] = L
    As = nextAs

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

Submission status: Accepted

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

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

    for i in range(n):
        if i == 0:
            a[i] = diff[0]
        else:
            a[i] = a[i - 1] + diff[i]
    
    if all([d == n for d in a]):
        break

print(' '.join([str(d) for d in a]))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k = map(int,readline().split())
A = list(map(int,readline().split()))

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

for i in range(k):
  m = n
  S = SegmentTree(n,0,lambda a, b: a+b)
  for j in range(n):
    q = A[j]
    m = min(m,q)
    S.update_add(max(1,j-q+1),min(n+1,j+q+2), 1)
  if i < k-1 and m >= n-1:
    A = [n]*n
    break
  for l in range(n):
    p = S.query(l+1)
    A[l] = p
    
print(*A)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

ans = [[0, A[i]] for i in range(N)]
idx = 1
for k in range(K):
    for i in range(N):
        ans[i][k%2] = 0
    for i in range(N):
        ans[max(0, i-ans[i][(k+1)%2])][k%2] += 1
        if i+ans[i][(k+1)%2] < N-1:
            ans[i+ans[i][(k+1)%2]+1][k%2] -= 1
    for i in range(N-1):
        ans[i+1][k%2] += ans[i][k%2]
    idx += 1
    idx %= 2
    if ans[0][k%2] == N:
        break

ans2 = [0]*N
for i in range(N):
    ans2[i] = ans[i][idx]
    
print(*ans2)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
dp = list(map(int,input().split()))
if k > 1000:
  ans = [n for _ in range(n)]
  print(*ans)
else:
  for i in range(k):
    ndp = [0 for _ in range(n)]
    for j in range(n):
      if j-dp[j] < 0:
        ndp[0] += 1
      else:
        ndp[j-dp[j]] += 1
      if j+dp[j]+1 < n:
        ndp[j+dp[j]+1] -= 1
    for j in range(1,n):
      ndp[j] += ndp[j-1]
    dp = ndp[:]
  print(*dp)

Submission status: Accepted

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: Accepted

Solution code:
"""
愚直にやるなら、操作のたびに、各座標ごとに照らしている電球の個数をカウントする。
1回の操作でこの作業をするのに、O(N^2)かかる。
K回やるなら、O(KN^2)かかる。

まず、各座標ごとに照らしている電球の個数はいくつか？というカウント作業を短縮する必要がある。
これを短縮しないと、初期状態の把握すら困難。
O(N)くらいでできないだろうか -> imosつかえばできる。


いや、各座標ごとに照らしている電球がいくつあるのかはそもそも把握不可能ではないのか？
長さNの配列を用意して、各座標ごとに


順番に1ずつ増えていく気配。
とりあえず、最初の配列の段階で


imosが使えるのでは？


で、これ最初全部の光の強さが0だとしても、操作はlogN+a回以内に終わる。
のでimosで毎回各座標を照らす電球の個数を計算していけば、答えにたどり着ける

"""

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

for _ in range(K):
    imos = [0]*(N+1)
    for i in range(N):
        d = A[i]
        #lは照らす範囲の左側
        l = max(0,i-d)
        #rは照らす範囲の右端
        r = min(N-1,i+d)

        #この辺、コーナーで間違える可能性あり
        ls = l
        lt = i
        rs = i+1
        rt = r+1
        imos[ls]+=1
        imos[lt]+=-1
        imos[rs]+=1
        imos[rt]+=-1
    for i in range(1,N):
        imos[i] += imos[i-1]
    #自分自身を照らすのをカウントに入れる
    for i in range(N):
        imos[i] += 1
    #Aを上書き
    A = imos
    if A.count(N)>=N:
        break
ans = []
for i in range(N):
    ans.append(str(A[i]))
print(" ".join(ans))

Submission status: Accepted

Solution code:
# coding: utf-8
import copy
N,K=map(int,input().split())
A=list(map(int,input().split()))
for k in range(K):
    imos=[0 for i in range(N+1)]
    
    for i in range(N):
        imos[max(i-A[i],0)]+=1
        imos[min(i+A[i]+1,N)]-=1
    tmp=[imos[0]]
    for i in range(N-1):
        tmp.append(tmp[i]+imos[i+1])
    A=copy.deepcopy(tmp)
    if set(A)==set([N]):
        break
    
print(*A)

Submission status: Accepted

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

for k in range(K):
    data = [0] * N
    for i in range(N):
        l = max(0, i-A[i])
        r = min(N-1, i+A[i])
        data[l] += 1
        if r+1 != N:
            data[r+1] -= 1
    ruiseki = [0] * N
    ruiseki[0] = data[0]
    for i in range(1, N):
        ruiseki[i] = ruiseki[i-1] + data[i]
    A = ruiseki
    if A == over:
        print(*A)
        exit()

print(*A)

Submission status: Accepted

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

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

inf = float('inf')
mod = 1000000007

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

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

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

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

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

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

	print(*A)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()