#P17738. 水果

水果

题目描述

你在超市里工作。

超市里有 nn 个水果,第 ii 个水果的美味度为 ii,价格为 cic_i,并且保证 cic_i 单调不降。

现在要把这 nn 个水果摆成一排放到货架上,第 jj 个位置摆的水果是 aja_j。但是你还没想好摆的顺序,所以可能会有 aj=−1a_j=-1,表示这个位置摆的水果未定。

在你决定了摆放顺序之后,一位顾客进来买水果。他会从第一个位置开始往后走,每当遇到一个美味度比之前都要高的水果时就会把它买下,直到看完第 kk 个位置后离开。

你希望选择一个最优的摆放顺序,使得这位顾客出的钱最多。

但是你并不知道 kk 是多少,因此你希望对每个 kk 都求出答案。你对不同的 kk 给出的顺序可以不同。

输入格式

第一行一个正整数 nn。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

第三行 nn 个正整数 c1,c2,…,cnc_1,c_2,\ldots,c_n。

输出格式

输出一行 nn 个正整数,表示 k=1,2,…,nk=1,2,\ldots,n 时的答案。

样例输入 1

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

样例输出 1

3 4 7 9 9

样例输入 2

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

样例输出 2

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

样例输入 3

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

样例输出 3

92 173 245 305 305 332 356 367 406 498

样例解释 1

  • k=1k=1 的最优方案是把第 55 个水果放第一个位置,即令 a1=5a_1=5,后面任意。
  • k=2k=2 的最优方案是令 a1=2a_1=2。
  • k=3k=3 的最优方案是令 a1=2,a3=5a_1=2,a_3=5。
  • k=4k=4 的最优方案是令 a1=2,a3=4,a4=5a_1=2,a_3=4,a_4=5。
  • k=5k=5 的最优方案是令 a1=2,a3=4,a4=5,a5=1a_1=2,a_3=4,a_4=5,a_5=1。

测试点约束

对于所有数据,保证 1≤n≤4×1051\le n\le 4\times10^5,−1≤ai≤n-1\le a_i\le n,ai≠0a_i\ne0,1≤ci≤1091\le c_i\le10^9,aa 中不存在两个相同的正整数,cc 单调不降。

子任务编号 特殊性质 分值
1 n≤8n\le8 10
2 a1=a2=⋯=an=−1a_1=a_2=\cdots=a_n=-1
3 n≤200n\le200 20
4 n≤2000n\le2000
5 c1=c2=⋯=cn=1c_1=c_2=\cdots=c_n=1
6 无