No.1332 Range Nearest Query
タグ : / 解いたユーザー数 96
作問者 :
penguinman
/ テスター :
yuto1115
Problem Statement
You are given $N$ coordinates $X_1,\ X_2,\ ...,\ X_N$ on a number line.
You are given $Q$ queries of the following form. Process them in order.
- You are given $2$ integers $l,\ r$ and a coordinate $x$. Find $\min(|X_l-x|,\ |X_{l+1}-x|,\ ...,\ |X_r-x|)$.
Notes
This problem has a strict time limit.
We have confirmed that the intended solution gets AC with PyPy3 (about $1500-2400$ms), but the same code submitted with Python3 got TLE.
Python users are recommended to submit with PyPy3.
Input
$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$
For convenience, $l,\ r,\ x$ in the $i$-th query are denoted by $l_i,\ r_i,\ x_i$, respectively.
The input satisfies the following constraints.
- $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$
- All input values are integers.
Output
On the $i$-th line, output the answer to the $i$-th query.
Sample
Sample 1
Input
2 1 2 3 2 2 1 1 1 3 1 2 3
Output
1 2 1
Output $|X_2-1|=|2-1|$ for the $1$-st query,
$|X_1-3|=|1-3|$ for the $2$-nd query,
and $min(|X_1-3|,\ |X_2-3|)=min(|1-3|,\ |2-3|)$ for the $3$-rd query.
Sample 2
Input
4 1 4 2 3 4 1 3 4 1 4 9 1 4 2 2 3 3
Output
0 5 0 1
Sample 3
Input
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
Output
52 86 2953 93 245 95
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。