問題一覧 > 通常問題

No.1332 Range Nearest Query

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

問題文

数直線上の $N$ 個の座標 $X_1,\ X_2,\ ...,\ X_N$ が与えられます。

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

  • $2$ 整数 $l,\ r$ と座標 $x$ が与えられる。$\min(|X_l-x|,\ |X_{l+1}-x|,\ ...,\ |X_r-x|)$ を求めよ。

注意

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

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

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

入力

$N$
$X_1\ X_2\ ...\ X_N$
$Q$
$l_1\ r_1\ x_1$
$l_2\ r_2\ x_2$
$:$
$l_Q\ r_Q\ x_Q$

便宜上 $i$ 番目のクエリにおける $l,\ r,\ x$ をそれぞれ $l_i,\ r_i,\ x_i$ としています。

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

  • $1≤N≤3×10^5$
  • $1≤Q≤10^5$
  • $1≤X_i≤10^9$
  • $X_i≠X_j(i≠j)$
  • $1≤l_i≤r_i≤N$
  • $1≤x_i≤10^9$
  • 入力は全て整数

出力

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

サンプル

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

$1$ 番目のクエリでは $|X_2-1|=|2-1|$ を、
$2$ 番目のクエリでは $|X_1-3|=|1-3|$ を、
$3$ 番目のクエリでは $min(|X_1-3|,\ |X_2-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もしくは右上の雲マークをクリックしてアカウントを作成してください。