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=[int(j)for j in input().split()]
a=[int(j)for j in input().split()]
if n<=k:
    print(*[n]*n)
    exit()
import copy
for _ in range(k):
    table=[0]*n
    for i in range(n):
        table[max(i-a[i],0)]+=1
        if i+a[i]+1<n:
            table[i+a[i]+1]-=1
    for i in range(1,n):
        table[i]+=table[i-1]
    a=copy.deepcopy(table)
    if a==[n]*n:
        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 new(a):
    if all([i == n for i in a]):
        print(*a)
        exit()
    res = [0] * (n+1)
    for k,v in enumerate(a):
        res[max(0,k-v)] += 1
        res[min(n,v+k+1)] -= 1
    return list(accumulate(res[:-1]))

for i in range(k):
    a = new(a)
print(*a)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


def naive(N, K, A):
    X = list(A)
    for _ in range(K):
        start = [0] * N
        end = [0] * N
        for i, x in enumerate(X):
            start[(max(0, i - x))] += 1
            end[min(i + x, N - 1)] += 1
        current = 0
        end_flag = True
        for i in range(N):
            current += start[i]
            X[i] = current
            if X[i] != N:
                end_flag = False
            current -= end[i]
        if end_flag:
            return X
    #     if all(x == N for x in X):
    #     print(X,start,end)
    #         return
    return X


def solve(N: int, K: int, A: "List[int]"):
    V = naive(N, K, A)
    print(' '.join(map(str, V)))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n,k = map(int,input().split())
A = list(map(int,input().split()))
# n = 2*10**5
# k = 40
# A = [0] * n

if k >= 41:
    print(*([n] * n))
else:
    for ii 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(1,len(B)):
            B[i] += B[i-1]
        A = B[:n]
    print(*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,read().split()))

def update(a):
    b = [0]*n
    for ind,i in enumerate(a):
        left = max(0,ind-i)
        right = ind+i+1
        b[left] += 1
        if(right<n):
            b[right] -= 1

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

    return b

for i in range(k):
    a = update(a)
    if(sum(a) == n*n):
        break

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class LazySegmentTree():
    def __init__(self, f, g, h, f_ie, g_ie, init_array):
        self.f = f
        self.g = g
        self.h = h
        self.f_ie = f_ie
        self.g_ie = g_ie

        l = len(init_array)
        self.size = 1 << (l - 1).bit_length()
        self.hight = self.size.bit_length()
        self.tree = [f_ie] * self.size + init_array + [f_ie] * (self.size - l)
        self.lazy = [g_ie] * (self.size * 2)

        self.chn = [0] * (self.size * 2)
        for i in range(self.size, self.size+l):
            self.chn[i] = 1
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = f(self.tree[i << 1], self.tree[(i << 1) | 1])
            self.chn[i] = self.chn[i << 1] + self.chn[(i << 1) | 1]

    def reflect(self, k):
        return self.tree[k] if self.lazy[k] == self.g_ie else self.g(self.tree[k], self.lazy[k], self.chn[k])

    def propagate(self, k):
        if self.lazy[k] == self.g_ie:
            return
        self.lazy[(k << 1) | 0] = self.h(self.lazy[(k << 1) | 0], self.lazy[k])
        self.lazy[(k << 1) | 1] = self.h(self.lazy[(k << 1) | 1], self.lazy[k])
        self.tree[k] = self.reflect(k)
        self.lazy[k] = self.g_ie

    def thrust(self, k):
        for i in range(self.hight, 0, -1):
            self.propagate(k >> i)

    def calc(self, k):
        while k != 0:
            k >>= 1
            self.tree[k] = self.f(self.reflect(
                k << 1), self.reflect((k << 1) | 1))

    def update(self, l, r, x):
        if l >= r:
            return

        l += self.size
        r += self.size

        self.thrust(l)
        self.thrust(r-1)

        a = l
        b = r
        while l < r:
            if l & 1:
                self.lazy[l] = self.h(self.lazy[l], x)
                l += 1
            if r & 1:
                r -= 1
                self.lazy[r] = self.h(self.lazy[r], x)
            l >>= 1
            r >>= 1
        self.calc(a)
        self.calc(b-1)

    def query(self, l, r):
        """
        reduce(f, a[l:r], ie)
        """

        if l >= r:
            return self.f_ie

        l += self.size
        r += self.size
        self.thrust(l)
        self.thrust(r-1)

        vl = self.f_ie
        vr = self.f_ie
        while l < r:
            if l & 1:
                vl = self.f(vl, self.reflect(l))
                l += 1
            if r & 1:
                 r -= 1
                 vr = self.f(self.reflect(r), vr)
            l >>= 1
            r >>= 1
        return self.f(vl, vr)

    def __print(self, a):
        cl = max(map(lambda x: len(str(x)), a[1:]))
        p = (r'|%' + str(cl) + r's')
        cl += 1
        for i in range(self.hight):
            j = 1 << i
            bc = (1 << (self.hight-i-1)) - 1
            s = ' ' + ' ' * ((cl+1) * bc)
            print(s.join(map(lambda x: p % x, a[j:j*2])))

    def print(self):
        print('tree')
        self.__print(self.tree)
        print('lazy')
        self.__print(self.lazy)


@mt
def slv(N, K, A):

    AA = A[:]
    from itertools import accumulate
    for _ in range(K):
        sa = [0] * N
        for i, d in enumerate(AA):
            sa[max(0, i-d)] += 1
            if i+d+1 < N:
                sa[i+d+1] -= 1
        AA = list(accumulate(sa))
        if min(AA) == N:
            break
    return AA


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(*slv(N, K, A))


    # N = 2*(10**5)
    # K = 2*(10**5)
    # A = [0] * N
    # print(*slv(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(K):
    imos = [0] * (N+1)
    for n,a in enumerate(A):
        left = max(0,n-a)
        right = min(N-1,n+a) + 1
        imos[left] += 1
        imos[right] -= 1
    cur = 0
    A = []
    for n in range(N):
        cur += imos[n]
        A.append(cur)
    if all([a==N for a in A]):
        break
print(*A)

Submission status: Accepted

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

for _ in range(k):
    imos = [0 for i in range(n+1)]
    for idx, a in enumerate(al):
        imos[max(idx-a, 0)] += 1
        imos[min(idx+a+1, n)] -= 1
    al = []
    now = 0
    for i in imos:
        now += i
        al.append(now)
    if len(set(al[:-1])) == 1 and al[0] == n:
        break

print(*al[:-1])

Submission status: Accepted

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

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




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

        if i+a[i]+1 < n:
            b[i+a[i]+1] -= 1
    
    judge = True
    tmp = 0
    for i in range(n):
        tmp += b[i]
        a[i] = tmp
        if tmp != n:
            judge = False
    if judge:
        break
print(*a)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()
dp = [0 for i in range(n)]
ans = [0 for i in range(n)]
for i in range(min(50,k)):
	for j in range(n):
		po = a[j]
		if j - po < 0:
			dp[0] += 1
		else:
			dp[j-po] += 1
		if j + po + 1 <= n-1:
			dp[j+po+1] -= 1
	a[0] = dp[0]
	for j in range(1,n):
		dp[j] += dp[j-1]
		a[j] = dp[j]
	for j in range(n):
		dp[j] = 0

if k <= 50:
	print(jo(a))
	exit()

for j in range(n):
	a[j] += k-51

for j in range(n):
	po = a[j]
	if j - po < 0:
		ans[0] += 1
	else:
		ans[j-po] += 1
	if j + po + 1 <= n-1:
		ans[j+po+1] -= 1
for j in range(1,n):
	ans[j] += ans[j-1]
print(jo(ans))

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(K):
    B = [0]*(N+1)
    for j in range(N):
        B[max(0,j-A[j])] += 1
        B[min(N,j+A[j]+1)] -= 1
    for j in range(N):
        A[j] = B[j]
        B[j+1] += B[j]
    if min(A) == 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(K):
    s = [0] * N
    e = [0] * N

    for j in range(N):
        s[max(j - A[j], 0)] += 1
        e[min(j + A[j], N-1)] += 1

    cur = 0
    for j in range(N):
        cur += s[j]
        A[j] = cur
        cur -= e[j]

    if s[0] == N and e[N-1] == N:
        break

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N,K = list(map(int,input().split()))
    A = list(map(int,input().split()))
    #A = [0]*1000
    #print(*A)
    #print(len(A))
    for k in range(min(K,200)):
        buf = [0]*N
        for i in range(N):
            if i-A[i]>=0:
                buf[i-A[i]] += 1
            else:
                buf[0] += 1
            if i+A[i]+1<N:
                buf[i+A[i]+1] -= 1
            #print(buf)

        #print(buf)

        b = 0
        B = []
        for i in range(N):
            b+=buf[i]
            B.append(b)

        A = B

    print(*A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

B = A.copy()
def update(A):
    res = [0]*N
    for i in range(N):
        if A[i]+i+1<N:
            res[A[i]+i+1] -= 1
        res[max(0,i-A[i])] += 1
    for i in range(N-1):
        res[i+1] += res[i]
    return res

while K:
    B = update(B)
    K -= 1
    if sum(B)==N**2:
        break

print(*B)

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from itertools import repeat
def main():
    n, k = map(int, stdin.readline().split())
    a = map(int, stdin.readline().split(), repeat(10, n))
    for i in xrange(min(k, 42)):
        b = [0] * (n + 1)
        for j, x in enumerate(a):
            l = j - x
            if l < 0:
                l = 0
            r = j + x + 1
            if r > n:
                r = n
            b[l] += 1
            b[r] -= 1
        s = 0
        for j in xrange(n):
            s += b[j]
            a[j] = s
    stdout.write(' '.join(map(str, a)))
    stdout.write('\n')
main()

Submission status: Accepted

Solution code:
def main():
	n,k=map(int,input().split())
	a=list(map(int,input().split()))
	for i in range(k):
		b=[0]*(n+1)
		for j in range(n):
			b[max(j-a[j],0)]+=1
			b[min(j+a[j]+1,n)]-=1
		for j in range(n):
			b[j+1]+=b[j]
		a=b[:n]
		if min(a)==n:
			break
	print(*a)
if __name__ == '__main__':
	main()

Submission status: Accepted

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

imos = [0]*n
for i in range(k):
    imos = [0]*(n+1)
    for j in range(n):
        mn = max(j-dp[j],0)
        mx = min(j+dp[j]+1,n)
        imos[mn]+=1
        imos[mx]-=1
    flag = True
    for j in range(n):
        dp[j]=imos[j]
        if(j>0):
            dp[j]+=dp[j-1]
        if dp[j]!=n:
            flag=False
    if flag:
        break
        
print(*dp)

Submission status: Accepted

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

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


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

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for loop in range(k):
    s = [0 for _ in range(n+2)]
    for i in range(1, n+1):
        s[max(0, i-a[i])] += 1
        s[min(n+1, i+1+a[i])] -= 1
    a[0]=0
    for i in range(1, n+1):
        s[i] += s[i-1]
    s[0] = 0
    s[-1] = 0
    a = s
    if sum(a) == n**2:
        break

print(*a[1:n+1])

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in edge]) for edge in self.edges]):
            print( [[nd for nd,d in edge] for edge in self.edges] )
        else:
            print(self)
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos
 
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)
 
show_flg=False
show_flg=True
ans=0



n,k=LI()
a=[0]+LI()+[0]
T=min(k,100)

for t in range(T):
    
    nx=[0]*(n+2)
    for i in range(1,n+1):
        l=max(0,i-a[i])
        r=min(i+a[i]+1,n+1)
        nx[l]+=1
        nx[r]+=-1
    #print(a,nx)
    for i in range(n+1):
        nx[i+1]+=nx[i]
    a=nx
print(*a[1:n+1])

Submission status: Accepted

Solution code:

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

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


for loop in range(K):

    if min(A) == N:
        break

    end = [0] * N
    now = 0
    nA = [0] * N

    for i in range(N):

        if i+A[i] < N:
            end[i+A[i]] += 1
        now += 1

        nA[i] += now

        now -= end[i]

    end = [0] * N
    now = 0

    for i in range(N-1,-1,-1):

        nA[i] += now

        if i-A[i] >= 0:
            end[i-A[i]] += 1
        now += 1
        
        now -= end[i]

    A = nA

#print (cnt)
print (*A)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import Counter

n, k = map(int, input().split())
a = [int(item) for item in input().split()]

for itr in range(k):
    diff = [0] * (n + 1)
    for i, val in enumerate(a):
        start = max(0, i - val)
        end = min(i + val + 1, n)
        diff[start] += 1
        diff[end] -= 1
    na = [0]
    for item in diff:
        na.append(na[-1] + item)
    a = na[1:-1]
    cnt = Counter(a)
    if cnt[n] == n:
        print(" ".join([str(n) for _ in range(n)]))
        exit()
print(" ".join([str(item) for item in a]))

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
M = min(100, K + 1)

DP = [[0] * N for _ in range(M)]

for i in range(N):
  DP[0][i] = A[i]

for i in range(1, M):
  for j in range(N):
    DP[i][max(0, j - DP[i-1][j])] += 1
    t = j + DP[i-1][j] + 1
    if t < N:
      DP[i][t] -= 1
  for j in range(1, N):
    DP[i][j] += DP[i][j-1]

print(" ".join(map(str, DP[-1])))

Submission status: Accepted

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

# a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################


#11-


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

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

for i in range(k):
    if(sum(a)==n*n):
        print(*([n]*n))
        exit()
    ud = [0 for j in range(n+1)]
    b = [0 for j in range(n)]
    
    for j in range(n):
        val = a[j]
        ud[max(0,j-val)]+=1
        ud[min(n,j+val+1)]-=1
    b[0] = ud[0]
    for j in range(1,n):
        b[j]=b[j-1]+ud[j]
    a = b

print(*a)

Submission status: Accepted

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

for i in range(k):
    nxt = [0]*n
    for j in range(n):
        l = j-a[j]
        r = j+a[j]+1
        if l < 0:
            l = 0
        nxt[l] += 1
        if r < n:
            nxt[r] -= 1
    for j in range(n-1):
        nxt[j+1] += nxt[j]
    if a == nxt:
        break
    a = nxt
print(*a)