C - Maximize Minimum
Editorial
/
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 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