题目描述
数直線上に電球が N 個並んでおり、電球には左から順に 1 から N までの番号がついています。 電球 i は座標 i にあります。
電球には光の強さを表す非負整数値が定まっており、 座標 x に光の強さ d の電球があるとき、その電球は座標 x−d−0.5 から座標 x+d+0.5 までの区間を照らします。 初めは電球 i の光の強さは Ai です。 そこで、以下の操作を K 回繰り返し行います。
- 1 以上 N 以下の各整数 i に対し、操作時に座標 i を照らしている電球の個数を Bi とする。そして、各電球 i の光の強さを Bi に変更する。
K 回の操作を行った後の各電球の光の強さを求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。
N K A1 A2 … AN
输出格式
K 回の操作を行った後の電球 i の光の強さ A′i を、以下の形式で標準出力に出力せよ。
A′1 A′2 … A′N
题目大意
Lamps
题目描述
给定 N 个灯泡,其亮度分别为 Ai。每个灯泡的作用范围为 i−Ai−0.5 到 i+Ai+0.5。
有 K 轮操作。
每轮操作使得每个灯泡的亮度更改为照亮它的灯泡的个数。
输入格式
输入格式如下
N
K
Ai
输出格式
输出更改后的 Ai
A′1 A′2 … A′N
样例 #1
样例输入 #1
5 1
1 0 0 1 0
样例输出 #1
1 2 2 1 2
样例 #2
样例输入 #2
5 2
1 0 0 1 0
样例输出 #2
3 3 4 4 3
提示
数据范围
- 1 ≦ N ≦ 2 × 105
- 1 ≦ K ≦ 2 × 105
- 0 ≦ Ai ≦ N
样例1解释
1 号数只有第 1 个数本身作用 ,第 2 个数有第 1 和 第 2 个数作用,以此类推。
5 1
1 0 0 1 0
1 2 2 1 2
5 2
1 0 0 1 0
3 3 4 4 3
提示
制約
- 1 ≦ N ≦ 2 × 105
- 1 ≦ K ≦ 2 × 105
- 0 ≦ Ai ≦ N
Sample Explanation 1
始めに座標 1 を照らしている電球は電球 1 のみであるので、操作後の電球 1 の強さは 1 になります。 また、始めに座標 2 を照らしている電球は電球 1 と電球 2 であるので、操作後の電球 2 の強さは 2 になります。