日本情報オリンピック 第4回 女性部門

2024年1月22日
情報オリンピック日本委員会

問題文

JOI 国では，今年プログラミングの世界大会が開かれることとなった．大会には N 人の選手が参加予定であり，選手には 1 から N までの番号が付けられている．

各選手の出身国は 1 以上 10⁹ 以下の整数の番号で表され，選手 i (1 ≦ i ≦ N) の出身国は国 C_i である．N 人の選手の出身国がすべて同じであることはない． また，各選手の座席は直線状に並んでおり，選手 i (1 ≦ i ≦ N) の座席は位置 X_i にある．選手 i (1 ≦ i ≦ N) と選手 j (1 ≦ j ≦ N) の座席の距離は |X_i - X_j| である．ただし，|x| は x の絶対値を表す．

各選手は大会中他の選手と交流をするにあたって，自分とは出身国の異なる選手のうち，自分と座席が最も近い選手までの座席の距離を知りたい．

各選手の出身国と座席の位置の情報が与えられたとき，各選手 i (1 ≦ i ≦ N) について，選手 i とは出身国の異なる選手のうち，選手 i との座席の距離が最も小さい選手までの座席の距離を出力するプログラムを作成せよ．

制約

• 2 ≦ N ≦ 300 000．
• 1 ≦ C_i ≦ 10⁹ (1 ≦ i ≦ N)．
• 1 ≦ X_i ≦ 10⁹ (1 ≦ i ≦ N)．
• N 人の選手の出身国がすべて同じであることはない．
• 入力される値はすべて整数である．

小課題

1. (20 点) N ≦ 1 000．
2. (40 点) C_i ≦ 10 (1 ≦ i ≦ N)．
3. (40 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N
C₁   X₁
C₂   X₂
︙
C_N   X_N

出力

N 行出力せよ．i 行目 (1 ≦ i ≦ N) には，選手 i とは出身国の異なる選手のうち，選手 i との座席の距離が最も小さい選手までの座席の距離を出力せよ．

入出力例

入力例 1
3
2 5
1 1
1 2

出力例 1
3
4
3

選手 1 の出身国は国 2 であり，選手 1 と出身国の異なる選手は選手 2, 3 である．これらの選手のうち，選手 1 との座席の距離が最も小さい選手は選手 3 であり，その座席の距離は 3 である．したがって，1 行目には 3 を出力する．
選手 2 の出身国は国 1 であり，選手 2 と出身国の異なる選手は選手 1 のみである．選手 2 と選手 1 の座席の距離は 4 なので，2 行目には 4 を出力する．
選手 3 の出身国は国 1 であり，選手 3 と出身国の異なる選手は選手 1 のみである．選手 3 と選手 1 の座席の距離は 3 なので，3 行目には 3 を出力する．

この入力例は小課題 1, 2, 3 の制約を満たす．

入力例 2
5
1 1
2 4
2 14
3 10
2 2

出力例 2
1
3
4
4
1

この入力例は小課題 1, 2, 3 の制約を満たす．

入力例 3
3
1 1
2 1
1 1

出力例 3
0
0
0

同じ位置に複数の選手の座席があることもある．

この入力例は小課題 1, 2, 3 の制約を満たす．