시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB421114.286%

문제

Supermarkets usually have fruits for sale in sections, where each section is dedicated to a single type of fruit. The supermarket that Benson the Rabbit is visiting has $N$ sections and $N$ types of fruits. The sections are numbered from $1$ to $N$ and each fruit is numbered from $1$ to $N$.

The $i$th fruit has tastiness $i$ and cost $C_i$. It is guaranteed that $C_i ≤ C_j$ for all $1 ≤ i < j ≤ N$.

Each of the $N$ sections is to be assigned a distinct type of fruit. At the moment, the type of fruit assigned to section $j$ is $A_j$. If $A_j = -1$, then section $j$ is empty. Otherwise, fruit $A_j$ is already assigned to section $j$. Once all $N$ fruits have been assigned, the supermarket will open and Benson will enter the supermarket to buy the fruits.

Benson is very picky but also in a rush, so he will visit the sections in increasing order. Benson’s basket is initially empty, and when he reaches a section, he will compare the tastiness of the fruit in that section to the tastiness of all of the fruits in his basket. If his basket is empty, or if the tastiness of the fruit at the current section is greater than the tastiness of every other fruit in his basket, Benson will add that fruit to his basket.

To maximise revenue, you have been tasked with assigning the fruits to the sections such that the sum of cost of fruits that Benson adds to his basket is maximised. As Benson is rushing for time, he might only visit the first few sections before going straight to the cashier. Help compute, for each $k$ from $1$ to $N$, the maximum possible revenue that can be achieved if Benson only visits the first $k$ sections given that the arrangement of fruits can change for different $k$.

입력

Your program must read from standard input.

The input starts with a line with one positive integer $N$.

The second line contains $N$ integers where the ith integer represents $A_i$.

The third line contains $N$ integers where the ith integer represents $C_i$.

출력

Your program must print to standard output.

The output should contain a $N$ integers on a single line. The kth one should be the maximum sum of costs that Benson will pay if the fruits are assigned optimally if he visits only the first $k$ sections.

제한

  • $1 ≤ N ≤ 400\,000$
  • $1 ≤ A_j ≤ N$ or $A_j = -1$
  • $1 ≤ C_i ≤ 10^9$
  • $C_i ≤ C_j$ for all $1 ≤ i < j ≤ N$

서브태스크

번호배점제한
16

$N ≤ 8$

25

$A_j = -1$ for all $0 ≤ j < n$

311

$N ≤ 200$

413

$N ≤ 2000$

523

$C_i = 1$ for all $0 ≤ i < n$

642

-

예제 입력 1

5
-1 -1 -1 -1 -1
1 1 1 1 1

예제 출력 1

1 2 3 4 5

We can arrange the fruits in increasing order $(1,2,3,4,5)$. Benson will take all fruits that he passes by, so for each $k$ from $1$ to $5$, Benson will take $k$ fruits which have a total cost of $k$.

This testcase is valid for all subtasks.

예제 입력 2

5
-1 3 -1 -1 -1
1 2 2 2 3

예제 출력 2

3 4 7 9 9

If Benson only visits the first section, it is optimal to put fruit $5$ in section $1$. This gives a cost of $3$.

If Benson only visits the first $2$ sections, it is optimal to put fruit $2$ in section $1$ and fruit $3$ in section $2$. This gives a cost of $2 + 2 = 4$.

If Benson only visits the first $3$ sections, it is optimal to put fruit $2$ in section $1$ and fruit $3$ in section $2$ and fruit $5$ in section $3$. This gives a cost of $2 + 2 + 3 = 7$.

If Benson visits either the first $4$ or all $5$ sections, it is optimal to put the fruits in the order $2$, $3$, $4$, $5$, $1$. This gives a cost of $2 + 2 + 2 + 3 = 9$.

This testcase is valid for subtasks 1, 3, 4 and 6.

예제 입력 3

13
-1 -1 5 6 -1 -1 7 11 -1 -1 10 -1 -1
1 1 1 1 1 1 1 1 1 1 1 1 1

예제 출력 3

1 2 3 4 5 6 6 7 8 9 9 9 9

This testcase is valid for subtasks 3, 4, 5 and 6.

예제 입력 4

10
-1 -1 -1 -1 5 -1 -1 -1 9 -1
5 11 24 27 35 60 72 81 91 92

예제 출력 4

92 173 245 305 305 332 356 367 406 498

This testcase is valid for subtasks 3, 4 and 6.

채점 및 기타 정보

  • 예제는 채점하지 않는다.