問題一覧 > 通常問題

No.3446 Range Adjacent Differences

レベル : / 実行時間制限 : 1ケース 2.200秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 8
作問者 : 👑 ArcAki / テスター : kidodesu
ProblemId : 13108 / 自分の提出
問題文最終更新日: 2026-02-16 20:22:48

注意

C++と同等程度の速度の言語を利用することを推奨します。

問題文

長さ $N$ の正整数列 $A$ が与えられ $i$ 番目は $A_i$ です。
$Q$ 個のクエリが与えられるのでそれぞれの答えを求めてください。
クエリ $i$

  • $1 ≤ L_i < R_i ≤ N$ なる $2$ 整数 $L_i, R_i$ と正整数 $X_i$、およびLもしくはRのどちらかの文字 $c_i$ が与えられます。
    数直線が存在し、$L_i ≤ j ≤ R_i$ なる整数 $j$ それぞれについて $A_j$ に点 $j$ が存在するとします。
    数直線上に並ぶ点を昇順に並べ替えた列を $B_1, B_2, \cdots, B_{R_i-L_i+1}$ とします。
    列 $B$ に対し $C$ を $C_j = B_{j+1}-B_j$ とした長さ $R_i-L_i$ の列とします。
    $c_i$ が Lのとき $C$ の要素であって $X_i$ 以下のもののうち最大のものを、
    Rのとき $C$ の要素であって $X_i$ 以上のもののうち最小のものをそれぞれ求め、存在しないならばそれを報告してください。

制約

  • $N, Q, A_i$ は整数である。
  • $2 ≤ N ≤ 10^5$
  • $1 ≤ Q ≤ 10^5$
  • $1 ≤ A_i ≤ 10^7$
  • クエリ $i$ について以下を満たす。
    • $L_i, R_i, X_i$ は整数である。
    • $c_i$ は L と R のいずれかである。
    • $1 ≤ L_i < R_i ≤ N$
    • $1 ≤ X_i ≤ 10^7$

入力

入力は以下の形式で標準入力より与えられる。 
$N\ Q$
$A_1\ A_2\ \cdots\ A_N$
$Query_1$
$\vdots$
$Query_Q$

ただし $Query_i$ はクエリ $i$ を表しそれぞれ以下の形式で与えられる。

$L_i\ R_i\ X_i\ c_i$

出力

$Q$ 行出力してください。$i$ 行目にはクエリ $i$ の答えとして、求めるものが存在するならその値を、そうでなければ $-1$ を出力し改行してください。

サンプル

サンプル1
入力
10 9
2 12 8 2 5 14 7 9 4 1
1 4 5 L
1 6 1 L
1 10 1 L
3 5 3 R
3 5 4 R
2 6 3 L
5 7 9 L
6 7 1 R
8 10 5 R
出力
4
0
1
3
-1
3
7
7
5

$1$ つ目のクエリについて $B = (2, 2, 8, 12),\ C = (0, 6, 4)$ となり、$5$ 以下で $C$ に含まれる最大の要素は $4$ となります。
$2$ つ目のクエリについて $B = (2, 2, 5, 8, 12, 14),\ C = (0, 3, 3, 4, 2)$ となり、 $1$ 以下で $C$ に含まれる最大の要素は $0$ です。
$5$ つ目のクエリのように条件を満たす要素が存在しない場合があることに注意してください。

サンプル2
入力
15 20
8405021 6691079 2900893 7996993 6932685 3015455 2328690 922936 5359848 5375935 4682031 9023559 2740593 5148957 6049734
14 15 7224326 R
2 13 543893 R
6 10 1780213 L
5 15 1875402 R
7 11 3391143 L
3 8 6317091 L
8 11 3399094 L
4 7 2829099 R
2 7 4063393 L
8 14 2839874 R
6 8 7563145 L
2 8 7022343 R
1 15 9146374 L
3 10 2492109 L
2 11 4770365 L
11 14 9656500 L
1 15 3293991 L
11 14 6135679 L
5 13 8728288 R
11 15 4335007 R
出力
-1
677817
1405754
2090874
2353341
3917230
677817
3917230
3675624
3647624
1405754
-1
1666576
2344393
1666576
3874602
1666576
3874602
-1
-1

サンプル3
入力
20 25
7 32 32 28 28 19 36 25 8 15 36 29 16 24 4 13 39 11 5 34
11 15 8 R
13 16 13 L
8 9 16 L
1 17 9 R
2 8 2 L
1 15 15 R
3 18 9 R
11 17 8 L
5 6 18 R
1 15 12 L
14 19 17 L
3 18 3 R
7 10 19 L
7 19 13 L
16 18 1 R
10 11 2 R
1 18 19 R
11 17 3 R
9 10 19 L
9 18 11 L
1 4 12 R
6 19 7 R
3 7 9 R
7 20 11 L
10 14 15 L
出力
8
9
-1
-1
0
-1
-1
8
-1
7
15
3
11
8
2
21
-1
3
7
8
21
7
9
8
8

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