← 返回题目列表

AtCoder · jsc2019_final_d

D. 最小化最大

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

配点 : 800 点

問題文

长度 小于或等于 N 整数序列 给出 A_0,A_1,\cdots,A_{N-1} 和 按字典顺序比较 B_0,B_1,\cdots,B_{N-1} 。 对于

全部 k (2 \leq k \leq N的问题)。 创建

  • 整数列 C_0,C_1,\cdots,C_{k-1} 。 在这里,所有 必须满足 i (0 \leq i \leq k-1), 计算A_i \leq C_i \leq B_i 。 ”C_{i+1}-C_i (0 \leq i \leq k-2) 的最大值的最小可能值是多少?

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq B_i \leq 10^9
  • 所有输入值都是整数。 如果您想走

入力

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

N
A_0 A_1 \cdots A_{N-1}
B_0 B_1 \cdots B_{N-1}

出力

N-1 行。i (1 \leq i \leq N-1) 行包含 作为第k=i+1 时打印问题的答案。 最小化


入力例 1

4
0 0 1 2
2 1 3 3

出力例 1

-2
0
1

各 k , 第C_{i+1}-C_i 最大值的整数序列 这是 C 的示例。

  • k=2: C=(2,0)
  • k=3: C=(1,1,1)
  • k=4: C=(1,1,1,2)

入力例 2

10
24 8 6 8 13 25 4 1 4 7
100 89 65 46 66 58 22 16 11 10

出力例 2

-92
-47
-30
-21
-10
-10
-10
-8
-4