No.3327 Shut Up, or I'll Throw a Polyomino at You
タグ : / 解いたユーザー数 55
作問者 :
のらら
/ テスター :
ゆにたりー卿
👑
DeltaStruct
Rice_tawara459
あじゃじゃ
bolero
Problem Statement
$N$ people who have never done competitive programming (hereafter called Earthlings) are standing in a row from left to right. The $i$-th Earthling from the left has number $i$ and a (self-proclaimed) rating of $A_i$.
Iwai Seijin throws a polyomino at Earthlings $Q$ times.
Specifically, the information for the $i$-th throw is given as a pair of $2$ integers ($c, X$), as follows.
- If $c=1$: throw a polyomino at the leftmost Earthling among those whose (self-proclaimed) rating is higher than $X$.
- If $c=2$: throw a polyomino at the rightmost Earthling among those whose (self-proclaimed) rating is higher than $X$.
An Earthling hit by a polyomino leaves the row and never returns to it afterwards.
For each of the $Q$ polyominoes thrown by Iwai Seijin, output the number of the Earthling who leaves the row because of it. However, if no one leaves the row, output $-1$.
Constraints
- $1 \leq N \leq 2×10^5$
- $1 \leq Q \leq 2×10^5$
- $1 \leq A_i, X \leq 10^9$
- $c \in \{1, 2\}$
- All inputs are integers.
Input
The input is given from standard input in the following format. Here, $query_i$ denotes the $i$-th query.
$N\ Q$ $A_1\ A_2\ ...\ A_N$ $query_1$ $query_2$ $:$ $query_Q$
Each query is given in the following format.
$c\ X$
Output
Output $Q$ lines.
On the $i$-th line, output the answer to the $i$-th query.
Sample
Sample 1
Input
5 4 3 5 8 1 4 1 4 2 7 2 4 1 3
Output
2 3 -1 5
The results of the queries are as follows.
- In the $1$-st query, Earthling number $2$ leaves the row.
- In the $2$-nd query, Earthling number $3$ leaves the row.
- In the $3$-rd query, no Earthling with a (self-proclaimed) rating greater than $4$ remains in the row, so no one leaves the row.
- In the $4$-th query, Earthling number $5$ leaves the row.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。