← 返回题目列表

Codeforces · 1661/D

D. 进展覆盖

中文机器翻译题面 查看原题

给定两个数组:一个由 $$$n$$$ 零组成的数组 $$$a$$$ 和一个由 $$$n$$$ 整数组成的数组 $$$b$$$。

您可以对数组 $$$a$$$ 应用以下操作任意次数:选择 $$$a$$$ 长度为 $$$k$$$ 的某个子段,并将算术级数 $$$1, 2, \ldots, k$$$ 添加到该子段 - i. e.将 $$$1$$$ 添加到子段的第一个元素,将 $$$2$$$ 添加到第二个元素,依此类推。所选子段应位于数组 $$$a$$$ 的边界内(即,如果所选子段的左边界为 $$$l$$$,则应满足条件 $$$1 \le l \le l + k - 1 \le n$$$)。请注意,添加的级数始终是 $$$1, 2, \ldots, k$$$,而不是 $$$k, k - 1, \ldots, 1$$$ 或其他任何内容(即,子段的最左侧元素始终增加 $$$1$$$,第二个元素始终增加 $$$2$$$,依此类推)。

您的任务是找到从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$ 满足条件 $$$a_i \ge b_i$$$ 所需的最小可能操作数。请注意,所有元素都应同时满足条件 $$$a_i \ge b_i$$$。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$) — 分别是两个数组中的元素数量和子段的长度。

输入的第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^{12}$$$),其中 $$$b_i$$$ 是数组 $$$b$$$ 的第 $$$i$$$ 个元素。

输出

打印一个整数 — 对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,满足条件 $$$a_i \ge b_i$$$ 所需的最小可能操作数。

示例

输入 #1

3 3
5 4 6

输出 #1

5

输入 #2

6 3
1 2 3 2 2 3

输出 #2

3

输入 #3

6 3
1 2 4 1 2 3

输出 #3

3

输入#4

7 3
50 17 81 25 42 39 96

输出#4

92

注意

考虑第一个例子。在这个测试中,我们实际上没有任何选择,因此我们需要添加至少五个级数以使第一个元素等于 $$$5$$$。数组 $$$a$$$ 变为 $$$[5, 10, 15]$$$。

考虑第二个例子。在此测试中,我们在 $$$[1; 段上添加一个进程3]$$$ 和 $$$[4 段上的两个级数; 6]$$$。然后,数组 $$$a$$$ 变为 $$$[1, 2, 3, 2, 4, 6]$$$。