長いだけのネクタイ(Just Long Neckties)

あなたはJust Odd Inventions 社を知っているだろうか?この会社の業務は「ただ奇妙な発明(just odd
inventions)」をすることである.ここでは略してJOI 社と呼ぶ.
JOI 社は新商品「長いだけのネクタイ」を開発した.ネクタイはN + 1 種類あり,各種類には1 からN + 1
までの番号がついている.i 番目(1 ≦i ≦N + 1) の種類のネクタイの長さはAi である.
JOI 社は社員を集め,ネクタイの試着会を行うことにした.試着会にはN 人の社員が参加し,j 人目
(1 ≦j ≦N) の社員がはじめに付けているネクタイの長さはBj である.
試着会は以下の手順で行われる予定である.
1. まず,試着会で使わないネクタイを1 種類選ぶ.
2. 次に,各社員はそれ以外のネクタイから試着するネクタイを1 種類選ぶ.ただし,どの2 人も同じ種
類のネクタイを選ばないようにする.
3. 最後に,各社員は今付けているネクタイを外し,先ほど選んだネクタイを試着する.
長さb のネクタイを付けていた社員が,長さa のネクタイを試着すると大きさmax{a −b, 0} の奇妙さを
感じる.
(ここで,max{a −b, 0} は,a −b と0 のうち小さくない方を表す.)試着会において各社員の感じ
る奇妙さの最大値を,その試着会の奇妙さとする.
試着会で使わないネクタイがk 番目の種類のネクタイのとき,試着会の奇妙さとして考えられる最小の
値をCk とする.
各種類のネクタイの長さ,各社員がはじめに付けているネクタイの長さが与えられたとき,C1,C2, . . . ,CN+1
の値を求めるプログラムを作成せよ.

• 1 ≦N ≦200 000.
• 1 ≦Ai ≦1 000 000 000 (1 ≦i ≦N + 1).
• 1 ≦Bj ≦1 000 000 000 (1 ≦j ≦N).

1. (1 点) N ≦10.
2. (8 点) N ≦2 000.
3. (91 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N
A1 . . . AN+1
B1 . . . BN

C1,C2, . . . ,CN+1 の値を,空白区切りで標準出力に1 行で出力せよ.

第19 回日本情報オリンピック(JOI 2019/2020) 本選
2020 年2 月9 日(茨城県つくば市)

생성자가 기록되지 않았습니다.

출처 JOI 2020 Final