C - The Kth Time Query
解説
/
実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
長さ N の数列 A = (a_1, a_2, \dots, a_N) があります。
以下で説明される Q 個のクエリに答えてください。
- クエリ i : 整数の組 (x_i, k_i) が与えられます。A の要素を a_1, a_2, \dots と前から順に見ていったときに、数 x_i が k_i 回目に登場するのは A の前から何番目の要素を見たときかを出力してください。
ただし条件を満たす要素が存在しない場合は -1 を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
- 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
- 1 \leq k_i \leq N (1 \leq i \leq Q)
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N Q a_1 a_2 \dots a_N x_1 k_1 x_2 k_2 \vdots x_Q k_Q
出力
Q 行出力せよ。i 行目ではクエリ i に対する答えを出力せよ。
入力例 1
6 8 1 1 2 3 1 2 1 1 1 2 1 3 1 4 2 1 2 2 2 3 4 1
出力例 1
1 2 5 -1 3 6 -1 -1
A の中で 1 は a_1, a_2, a_5 に登場します。よって、クエリ 1 からクエリ 4 の答えは順に 1, 2, 5, -1 となります。
入力例 2
3 2 0 1000000000 999999999 1000000000 1 123456789 1
出力例 2
2 -1
Score : 300 points
Problem Statement
We have a sequence of N numbers: A = (a_1, a_2, \dots, a_N).
Process the Q queries explained below.
- Query i: You are given a pair of integers (x_i, k_i). Let us look at the elements of A one by one from the beginning: a_1, a_2, \dots Which element will be the k_i-th occurrence of the number x_i?
Print the index of that element, or -1 if there is no such element.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
- 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
- 1 \leq k_i \leq N (1 \leq i \leq Q)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q a_1 a_2 \dots a_N x_1 k_1 x_2 k_2 \vdots x_Q k_Q
Output
Print Q lines. The i-th line should contain the answer to Query i.
Sample Input 1
6 8 1 1 2 3 1 2 1 1 1 2 1 3 1 4 2 1 2 2 2 3 4 1
Sample Output 1
1 2 5 -1 3 6 -1 -1
1 occurs in A at a_1, a_2, a_5. Thus, the answers to Query 1 through 4 are 1, 2, 5, -1 in this order.
Sample Input 2
3 2 0 1000000000 999999999 1000000000 1 123456789 1
Sample Output 2
2 -1