← 返回题目列表

AtCoder · otemae2019_c

C. 整理卡 2

中文机器翻译题面 查看原题

配点: 100 点

問題

皮塔罗是 一套 N 卡片。 2 我有一套。1 第一套卡片包括 它被命名为 A ,并按从头开始的顺序 写入数字 a_1 如果要将其更改为输出最多为 a_N 。2 第一套卡片包括 它被命名为 B ,并按从头开始的顺序 写入数字 b_1 如果要将其更改为输出最多为 b_N 。

皮塔罗卡片套装 您可以随时重新排列 B ,次数不限。

Pitaro 玩以下游戏。 执行 N 次。

  • i (1 \leq i \leq N) 第二场比赛。卡组 A 开始 i 按顺序写在纸张上的一系列数字。 C_i 。
  • 卡组 B 通过按顺序排列每张卡片上写的数字来创建数字序列。 卡片设置为最大化 C_i 连续出现的次数 排序 B 。
  • 但是,C_i 它们的出现位置不得重叠。例如,一个数列 {1 2 1 2 1 2 1 2} 是 {(1 2 1 2) (1 2 1 2)} 如果我们考虑序列 它已出现 {1 2 1 2} 是 从 2 次。这时,{(1 2 1 2) 1 2 1 2} ,{1 2 (1 2 1 2) 1 2} ,{1 2 1 2 (1 2 1 2)} 的 3 无法计数。 游戏的得分是
  • 卡组 B 通过按顺序排列每张卡片上写的数字来创建数字序列。 卡片设置为最大化 C_i 连续出现的次数。

编写一个程序来查找 Pitaro 在每场比赛中可以获得的分数。

制約

  • 所有输入均为整数。
  • 2 \leq N \leq 100\,000.
  • 1 \leq a_i, b_i \leq 100\,000 (1 \leq i \leq N).

小課題

  1. (16 点) N \leq 8.
  2. (10 点) a_i = 1 (1 \leq i \leq N).
  3. (24 点) N \leq 1\,000.
  4. (50 点)没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

N
a_1 a_2 \cdots a_N
b_1 b_2 \cdots b_N

出力

到标准输出N 行。i (1 \leq i \leq N) 行包含i 输出Pitaro在第二场比赛中可以获得的分数。 通过使用


入力例 1

5
1 2 3 4 5
1 2 2 1 3

出力例 1

2
2
1
0
0

例如 当计算像 {1 2 3 2 1} 排序 可能会出现 C_1 从 2 個,{3 1 2 1 2} 排序 可能会出现 C_2 从 2 個,{2 1 2 3 1} 排序 可能会出现 C_3 从 1 。

这个输入/输出示例是一个小任务。 1,3,4 很满意。 从


入力例 2

5
1 1 1 1 1
1 1 1 1 1

出力例 2

5
2
1
1
1

卡组 B 获得的可能序列是 只有 {1 1 1 1 1} 。

这个输入/输出示例是一个小任务。 1,2,3,4 很满意。 从