Water Tank

题目描述

给定长度为 $N$ 的正整数序列：$H=(H _ 1,H _ 2,\dotsc,H _ N)$。 存在一个长度为 $N+1$ 的非负整数序列：$A=(A _ 0,A _ 1,\dotsc,A _ N)$。最初，$A _ 0=A _ 1=\dotsb=A _ N=0$。 对 $A$ 重复执行以下操作：

将 $A _ 0$ 的值增加 $1$。 按顺序对 $i=1,2,\ldots,N$ 执行以下操作： 如果 $A _ {i-1}\gt A _ i$ 且 $A _ {i-1}\gt H _ i$，则将 $A _ {i-1}$ 的值减 $1$ 并将 $A _ i$ 的值加 $1$。

对于每个 $i=1,2,\ldots,N$，找出在首次满足 $A _ i>0$ 之前所进行的操作次数。

输入格式

输入从标准输入按以下格式给出： $N$ $H _ 1$ $H _ 2$ $\dotsc$ $H _ N$

输出格式

输出 $i=1,2,\ldots,N$ 的答案，所有答案在一行中以空格分隔。

5
3 1 4 1 5

4 5 13 14 26

6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

1000000001 2000000001 3000000001 4000000001 5000000001 6000000001

15
748 169 586 329 972 529 432 519 408 587 138 249 656 114 632

749 918 1921 2250 4861 5390 5822 6428 6836 7796 7934 8294 10109 10223 11373

提示

$1\leq N\leq2\times10 ^ 5$ $1\leq H _ i\leq10 ^ 9\ (1\leq i\leq N)$ 所有输入值均为整数。

有一个很长的水槽，等间距放置了高度不同的隔板。当从水槽的一端注水时，Takahashi 想知道水到达由这些隔板分隔的每一段的时间。

</blockquote>前五次操作如下所示。 这里，每一行对应一次操作，最左列表示步骤 1，其他列表示步骤 2。 从该图可知，$A _ 1\gt0$ 第一次出现在第 4 次操作之后，$A _ 2\gt0$ 第一次出现在第 5 次操作之后。 类似地，$A _ 3, A _ 4, A _ 5$ 的答案分别为 $13, 14, 26$。 因此，应输出 $4 5 13 14 26$。
注意要输出的值可能无法用 32 位整数表示。

标签: AtCoder|abc359E

来源

AtCoder|abc359E