No.3446 Range Adjacent Differences
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
LorR.
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$ isL, find the largest element of $C$ that is at most $X_i$;
if it isR, 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
LorR. - $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もしくは右上の雲マークをクリックしてアカウントを作成してください。
kidodesu