問題一覧 > 通常問題

No.3446 Range Adjacent Differences

レベル : / AI推定難易度 : 2575 / 実行時間制限 : 1ケース 2.200秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 9
作問者 : 👑 ArcAki / テスター : kidodesu
お気に入りにしたユーザー ProblemId : 13108 / 自分の提出
問題文最終更新日: 2026-02-16 20:22:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Note

We recommend using a language with speed comparable to C++.

Problem Statement

You are given a sequence $A$ of positive integers of length $N$, whose $i$-th element is $A_i$.
You are given $Q$ queries; find the answer to each of them.
Query $i$

  • You are given $2$ integers $L_i, R_i$ satisfying $1 ≤ L_i < R_i ≤ N$, a positive integer $X_i$, and a character $c_i$ which is either L or R.
    Suppose there is a number line, and for each integer $j$ with $L_i ≤ j ≤ R_i$, point $j$ is located at $A_j$.
    Let $B_1, B_2, \cdots, B_{R_i-L_i+1}$ be the sequence obtained by sorting the points on the number line in ascending order.
    For the sequence $B$, let $C$ be the sequence of length $R_i-L_i$ defined by $C_j = B_{j+1}-B_j$.
    If $c_i$ is L, find the largest element of $C$ that is at most $X_i$;
    if it is R, find the smallest element of $C$ that is at least $X_i$. If no such element exists, report that.

Constraints

  • $N, Q, A_i$ are integers.
  • $2 ≤ N ≤ 10^5$
  • $1 ≤ Q ≤ 10^5$
  • $1 ≤ A_i ≤ 10^7$
  • For query $i$, the following hold.
    • $L_i, R_i, X_i$ are integers.
    • $c_i$ is either L or R.
    • $1 ≤ L_i < R_i ≤ N$
    • $1 ≤ X_i ≤ 10^7$

Input

The input is given from standard input in the following format.
$N\ Q$
$A_1\ A_2\ \cdots\ A_N$
$Query_1$
$\vdots$
$Query_Q$

Here, $Query_i$ represents query $i$, and each is given in the following format.

$L_i\ R_i\ X_i\ c_i$

Output

Output $Q$ lines. On the $i$-th line, as the answer to query $i$, output the requested value if it exists, and $-1$ otherwise, followed by a newline.

Sample

Sample 1
Input
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
Output
4
0
1
3
-1
3
7
7
5

For the $1$st query, $B = (2, 2, 8, 12),\ C = (0, 6, 4)$, and the largest element of $C$ that is at most $5$ is $4$.
For the $2$nd query, $B = (2, 2, 5, 8, 12, 14),\ C = (0, 3, 3, 4, 2)$, and the largest element of $C$ that is at most $1$ is $0$.
Note that, as in the $5$th query, there may be no element satisfying the condition.

Sample 2
Input
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
Output
-1
677817
1405754
2090874
2353341
3917230
677817
3917230
3675624
3647624
1405754
-1
1666576
2344393
1666576
3874602
1666576
3874602
-1
-1

Sample 3
Input
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
Output
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もしくは右上の雲マークをクリックしてアカウントを作成してください。