DMOPC '20 Contest 4 P4 - Javelin Throwing - Olympiads Online Judge

DMOPC '20 Contest 4 P4 - Javelin Throwing

Points: 15 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Problem type

Alice is training for an upcoming javelin-throwing competition! The javelin-throwing field can be modelled as a 1-D line, with Alice standing at the coordinate $0$ $0$ .

Alice throws $N$ $N$ javelins in the positive direction. When she throws a javelin, it lands at some real-valued point on the field, making a hole there. It's possible for the javelin to land exactly in a previously made hole, in which case no new hole is made. Holes are permanent, and there are initially no holes in the field.

Right after the $i^\text{th}$ $i^{th}$ throw, Alice counts $a_i$ $a_{i}$ and $b_i$ $b_{i}$ , the number of holes strictly behind and strictly in front of the javelin she just threw (respectively). She then tells you $a_i$ $a_{i}$ . You don't know anything else about her throws.

Given the information you have right after the $i^\text{th}$ $i^{th}$ throw, what is the minimum possible value of $\sum_{j=1}^i b_j$ $\sum_{j = 1}^{i} b_{j}$ ?

Constraints

$0 \le a_i < i$ $0 \leq a_{i} < i$

Subtask 1 [15%]

$1 \le N \le 5000$ $1 \leq N \leq 5000$

Subtask 2 [85%]

$1 \le N \le 2 \times 10^6$ $1 \leq N \leq 2 \times 10^{6}$

Input Specification

The first line contains an integer $N$ $N$ , the number of throws.

The second line contains $N$ $N$ space-separated integers, $a_1, a_2, \dots, a_N$ $a_{1}, a_{2}, \dots, a_{N}$ .

Output Specification

Output $N$ $N$ space-separated integers. The $i^\text{th}$ $i^{th}$ integer should be the minimum possible value of $\sum_{j=1}^i b_j$ $\sum_{j = 1}^{i} b_{j}$ , given that you know $a_1$ $a_{1}$ through $a_i$ $a_{i}$ .

Sample Input 1

Copy

3
0 0 2

Sample Output 1

Copy

0 0 1

Explanation for Sample 1

There are no holes in front of throw $1$ $1$ :

$\text{[math]}$

So the first answer is $0$ $0$ .

On throw $2$ $2$ , you know that $a_1 = a_2 = 0$ $a_{1} = a_{2} = 0$ . It's possible that both throws landed at exactly the same point, in which case there would be no holes in front of either throw:

$\text{[math]}$

So the second answer is $0 + 0 = 0$ $0 + 0 = 0$ .

However, you then learn that there were $2$ $2$ holes behind throw $3$ $3$ . So the second throw must have landed behind the first, and the only solution would be

$\text{[math]}$

for an answer of $0 + 1 + 0 = 1$ $0 + 1 + 0 = 1$ .

Sample Input 2

Copy

6
0 1 0 3 0 2

Sample Output 2

Copy

0 0 1 2 5 6

Sample Input 3

Copy

5
0 1 2 1 2

Sample Output 3

Copy

0 0 0 1 1

Comments

0

Riolku commented on March 17, 2021, 12:35 a.m. ← edited →

Data were updated post-contest to break some unintended solutions.

1

Plasmatic commented on March 17, 2021, 3:25 a.m.

:^)