← 返回题目列表

AtCoder · joi2020ho_a

A. 只是长领带

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

配点: 100 点

你听说过 Just Odd Inventions 吗?这家公司的业务就是制造“只是奇怪的发明”。在这里,我们将其缩写为J​​OI。

JOI 开发了一种新产品“长领带”。领带是 N + 1 有不同的类型,每种类型都有 它们的编号最大为 1 从 N + 1 。i 番目 (1 \leqq i \leqq N + 1) 领带长度类型为 A_i 。

JOI决定召集所有员工,举办一场平局比赛活动。在试衣活动中 N 员工参与,j 人目 (1 \leqq j \leqq N) 的员工最初佩戴的领带长度为 B_j 。

试衣活动将按照以下程序举行。

  1. 首先,选择一条不会在试衣活动中使用的领带。 1 选择类型。
  2. 接下来,每位员工从其他领带中选择一条领带进行试戴。 1 选择类型。然而,哪 2 人们还应避免选择同一类型的领带。
  3. 最后,每位员工摘下他们当前佩戴的领带,并试戴他们之前选择的领带。

长度 一名打着 b 领带的员工 当您试戴 a 领带时,您会发现它的尺寸。 我感觉到 \max\{a − b, 0\} 的奇怪。 (这里,\max\{a − b, 0\} 是 表示a - b 和 我讨厌 0 的非较小者。 ) 试衣活动中每位员工感受到的陌生感最大值计算如下:奇怪。

试穿活动中不会使用的领带 对于 k 类型的领带,让我们计算试衣过程中可能出现的最小奇怪程度。 C_k 。

给定每种领带的长度以及每个员工最初佩戴的领带的长度, 编写一个程序来查找C_1, C_2, \ldots, C_{N + 1} 的值。


入力

输入是按以下格式从标准输入给出的。所有输入值都是整数。

N
A_1 \cdots A_{N + 1}
B_1 \cdots B_N

出力

C_1, C_2, \ldots, C_{N + 1} 的值被发送到标准输出,并以空格分隔。 输出为 1 行。


制約

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq A_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N + 1).
  • 1 \leqq B_j \leqq 1\,000\,000\,000 (1 \leqq j \leqq N).

小課題

  1. (1 点) N \leqq 10.
  2. (8 点) N \leqq 2\,000.
  3. (91 点)没有额外的限制。

入力例 1

3
4 3 7 6
2 6 4

出力例 1

2 2 1 1

例如,如下举行试穿会。 我们不会使用

  • 4 类型的领带。
  • 社員 1 是 1 th,员工 选择 2 是 2 th,员工 选择 3 是 3 领带类型。
  • 每个员工都试穿衣服。

此时,每个员工依次感受到了异样。 2, 0, 3 因此,这次拟合事件的奇怪之处在于 3 。

通过改变员工选择的领带来减少试穿过程中的奇怪现象。 它可以是 1 。例如,假设您举办如下试穿活动。

  • 4 类型的领带。
  • 社員 1 是 2 th,员工 选择 2 是 3 th,员工 选择 3 是 1 领带类型。
  • 每个员工都试穿衣服。

此时,每个员工依次感受到了异样。 1, 1, 0 因此,这次拟合事件的奇怪之处在于 1 。

这是 当不使用第 4 种领带时,试衣过程中的奇怪程度最小,因此C_4 = 1 。


入力例 2

5
4 7 9 10 11 12
3 5 7 9 11

出力例 2

4 4 3 2 2 2