No.2223 Merged Med
タグ : / 解いたユーザー数 22
作問者 :
stoq
/ テスター :
nok0
Problem Statement
The beauty of a sequence $X=(X_1,\dots,X_k)$ is defined as follows.
- Choose $(l,r) \ (1 \leq l \leq r \leq k)$ and create a sequence $X'$ of length $k+l-r$ by replacing $X_l,\dots,X_r$ in $X$ with the single element ${\rm Med}(X_l,\dots ,X_r)$.
The beauty of $X$ is the minimum value of ${\rm Med}(X')$ over all possible such $X'$.
Here, for $Y=(Y_1,\dots,Y_k)$, ${\rm Med}(Y)$ denotes the median of $Y_1,\dots,Y_k$, that is, the $\displaystyle \left \lfloor \frac{k}{2} \right \rfloor +1$-th element when $Y_1,\dots,Y_k$ are sorted in ascending order.
You are given a sequence $(A_1,\dots,A_N)$ of length $N$.
Process the following $Q$ queries.
$l$ $r$
- Output the beauty of the sequence $(A_l,\dots,A_r)$.
Input
$N$ $Q$ $A_1$ $\dots$ $A_N$ $l_1$ $r_1$ $\vdots$ $l_Q$ $r_Q$
- All input values are integers.
- $1 \leq N \leq 5 \times 10^4$
- $1 \leq Q \leq 5 \times 10^4$
- $1 \leq A_i \leq N$
- $1 \leq l_i \leq r_i \leq N$
Output
Output the answer to each query, separated by newlines.
Sample
Sample 1
Input
5 3 1 5 3 4 2 1 5 2 3 1 1
Output
2 5 1
For the $1$st query, for example, replacing $A_2,A_3,A_4$ with their median gives $(1,\ 4,\ 2)$, whose median is $2$.
There is no way to make the median smaller than this, so the beauty of $(A_1,\dots,A_5)$ is $2$.
For the $2$nd query, for example, replacing $A_2,A_3$ with their median gives $(5)$, whose median is $5$.
There is no way to make the median smaller than this, so the beauty of $(A_2,A_3)$ is $5$.
Sample 2
Input
3 3 3 3 3 1 3 2 3 3 3
Output
3 3 3
$A_i$ are not necessarily distinct.
Sample 3
Input
20 10 1 6 6 19 13 10 20 1 8 11 12 4 7 3 10 20 19 13 14 13 1 20 2 13 6 7 5 16 9 13 12 14 11 13 10 13 2 14 6 17
Output
6 6 20 10 7 4 7 7 6 10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。