103594: [Atcoder]ABC359 E - Water Tank

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：9 Solved：0

Description

Score : $500$ points

Story

There is a long water tank with boards of different heights placed at equal intervals. Takahashi wants to know the time at which water reaches each section separated by the boards when water is poured from one end of the tank.

Problem Statement

You are given a sequence of positive integers of length $N$: $H=(H _ 1,H _ 2,\dotsc,H _ N)$.

There is a sequence of non-negative integers of length $N+1$: $A=(A _ 0,A _ 1,\dotsc,A _ N)$. Initially, $A _ 0=A _ 1=\dotsb=A _ N=0$.

Perform the following operations repeatedly on $A$:

  1. Increase the value of $A _ 0$ by $1$.
  2. For $i=1,2,\ldots,N$ in this order, perform the following operation:
    • If $A _ {i-1}\gt A _ i$ and $A _ {i-1}\gt H _ i$, decrease the value of $A _ {i-1}$ by 1 and increase the value of $A _ i$ by $1$.

For each $i=1,2,\ldots,N$, find the number of operations before $A _ i>0$ holds for the first time.

Constraints

  • $1\leq N\leq2\times10 ^ 5$
  • $1\leq H _ i\leq10 ^ 9\ (1\leq i\leq N)$
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$H _ 1$ $H _ 2$ $\dotsc$ $H _ N$

Output

Print the answers for $i=1,2,\ldots,N$ in a single line, separated by spaces.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

4 5 13 14 26

The first five operations go as follows.

Here, each row corresponds to one operation, with the leftmost column representing step 1 and the others representing step 2.

From this diagram, $A _ 1\gt0$ holds for the first time after the 4th operation, and $A _ 2\gt0$ holds for the first time after the 5th operation.

Similarly, the answers for $A _ 3, A _ 4, A _ 5$ are $13, 14, 26$, respectively.

Therefore, you should print 4 5 13 14 26.

Sample Input 2

6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

1000000001 2000000001 3000000001 4000000001 5000000001 6000000001

Note that the values to be output may not fit within a $32$-bit integer.

Sample Input 3

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

Sample Output 3

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

Output

得分：500分 故事： 有一条长水箱，每隔相等的距离放置着高度不同的板子。高桥想要知道当水从水箱一端倒入时，每块板子分隔出的区域分别在何时会被水淹没。 问题描述： 给你一个长度为 $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$ 上反复执行以下操作： 1. 将 $A_0$ 的值增加1。 2. 从 $i=1,2,\ldots,N$ 的顺序，执行以下操作： - 如果 $A_{i-1}>A_i$ 且 $A_{i-1}>H_i$，则将 $A_{i-1}$ 的值减小1，同时将 $A_i$ 的值增加1。 对于每个 $i=1,2,\ldots,N$，找出在 $A_i>0$ 首次成立之前执行了多少次操作。 限制条件： - $1\leq N\leq2\times10^5$ - $1\leq H_i\leq10^9\ (1\leq i\leq N)$ - 所有输入值都是整数。 输入： 输入通过标准输入给出以下格式： $N$ $H_1$ $H_2$ $\dotsc$ $H_N$ 输出： 在一行内打印出对于 $i=1,2,\ldots,N$ 的答案，用空格分隔。 样例输入1： 5 3 1 4 1 5 样例输出1： 4 5 13 14 26 注：从图中可以看出，$A_1>0$ 在第4次操作后首次成立，$A_2>0$ 在第5次操作后首次成立。$A_3, A_4, A_5$ 的答案分别是 $13, 14, 26$。 样例输入2： 6 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 样例输出2： 1000000001 2000000001 3000000001 4000000001 5000000001 6000000001 注意：输出的值可能超出32位整数的范围。 样例输入3： 15 748 169 586 329 972 529 432 519 408 587 138 249 656 114 632 样例输出3： 749 918 1921 2250 4861 5390 5822 6428 6836 7796 7934 8294 10109 10223 11373

Source/Category

加入题单

算法标签：