問題一覧 > 通常問題

No.1332 Range Nearest Query

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 83
作問者 : penguinman / テスター : yuto1115
8 ProblemId : 5229 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-01-24 01:47:23

問題文

数直線上の N 個の座標 X1, X2, ..., XN が与えられます。

以下のクエリが Q 個与えられるので、順に処理してください。

  • 2 整数 l, r と座標 x が与えられる。min(|Xl−x|, |Xl+1−x|, ..., |Xr−x|) を求めよ。

注意

時間制限の厳しい問題になっております。

PyPy3 による想定解の AC は確認しておりますが（1500−2400ms 程度）、同様のコードを Python3 で投げたところ TLE しました。

Python ユーザーの方には PyPy3 による提出を推奨します。

入力

N
X1 X2 ... XN
Q
l1 r1 x1
l2 r2 x2
:
lQ rQ xQ

便宜上 i 番目のクエリにおける l, r, x をそれぞれ li, ri, xi としています。

入力は以下の制約を満たします。

  • 1≤N≤3×105
  • 1≤Q≤105
  • 1≤Xi≤109
  • Xi≠Xj(i≠j)
  • 1≤li≤ri≤N
  • 1≤xi≤109
  • 入力は全て整数

出力

i 行目には、i 番目のクエリに対する答えを出力してください。

サンプル

サンプル1
入力
2
1 2
3
2 2 1
1 1 3
1 2 3
出力
1
2
1

1 番目のクエリでは |X2−1|=|2−1| を、
2 番目のクエリでは |X1−3|=|1−3| を、
3 番目のクエリでは min(|X1−3|, |X2−3|)=min(|1−3|, |2−3|) を出力します。

サンプル2
入力
4
1 4 2 3
4
1 3 4
1 4 9
1 4 2
2 3 3
出力
0
5
0
1

サンプル3
入力
5
100 291 15 57 100000
6
1 4 343
3 3 101
4 5 3010
1 5 193
3 5 302
1 2 195
出力
52
86
2953
93
245
95

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。