← 返回题目列表

AtCoder · jsc2019_final_c

C. 最大化最小值

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

配点 : 700 点

問題文

高桥君好长 我在 L 旁边有一个长蛋糕。 距蛋糕左边缘的距离 将点 x 设置为坐标 我们将其称为 x 点。 一开始,在这个蛋糕上 1 只放置了一颗草莓,其坐标为 X 。

从现在开始,高桥君将 执行N 操作。 具体来说,i (0 \leq i \leq N-1) 在第二个操作中,执行以下操作: 如果

  • 座標 A_i 处没有放置草莓:坐标 将草莓放在 A_i 上。 如果草莓放置在
  • 座標 A_i :坐标 取出 A_i 中的草莓。

每次操作后,将 2 保证至少有一颗草莓。

一个蛋糕美丽 定义如下。

  • 当您可以随意多次执行以下操作时, 2 两个草莓之间的距离的最大可能值决定了蛋糕的美观程度。 放置在
    • 座標 x 的草莓是 转至 L-x 。请注意,如果目的地放置了另一个草莓,则无法执行此操作。

全部 i (0 \leq i \leq N-1),i 看看第二次手术后蛋糕的美丽程度。 另外,为了追求蛋糕的美观,我们实际上并没有动草莓。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L \leq 10^9
  • 0 \leq X \leq L
  • 0 \leq A_i \leq L
  • 全部 i (0 \leq i \leq N-1),i 第二次操作后在蛋糕上面。 2 草莓多了三个。
  • 所有输入值都是整数。 输出

入力

输入将以以下形式通过标准输入给出。

N L X
A_0
A_1
\vdots
A_{N-1}

出力

N 行。i+1 (0 \leq i \leq N-1) 行包含i 第一次操作后输出蛋糕的美丽。


入力例 1

5 10 0
6
9
3
0
3

出力例 1

6
4
3
3
5

例如, 给定一个数字序列1 当第二个操作完成时,有一个 3 放置了两个草莓,它们的坐标是 0,6,9 。 坐标 将草莓坐标在 6 如果将其移动到 4 ,草莓的坐标将是 0,4,9 。 这时,“最近的 2 两个草莓之间的距离是 4 ,这是最大值。 因此,这款蛋糕的美妙之处在于 4 。


入力例 2

10 10 7
10
2
6
2
10
4
1
4
10
3

出力例 2

7
3
2
3
3
1
1
3
3
1