BBIN2 - Búsqueda Binaria 2
Given an array of N integers in non-decreasing order, you're going to receive Q queries. Each of them contains a single integer. For each query use binary search to respond with the index of the last occurence of the given integer in the array.
Input
In the first line there is an integer N (1 <= N <= 10^5) and an integer Q (1 <= Q <= 10^5).
In the second line, N integers separated by a single space. Each integer takes a values between 1 and 10^9.
Then Q lines follows, each one with an integer between 1 and 10^9, representing a query.
Output
For each query (in the same order they were given) print a line with a single integer, the index of the last occurence of the corresponding element, or -1 if it is not in the given array.
Example
Input:
10 4
1 3 4 5 5 6 7 8 8 17
3
5
9
1
Output:
1
4
-1
0
hide comments
solvertobe:
2019-06-29 08:12:03
Easy binary search. What if it's required to find the index of the i_th occurrence of some x, if there isn't i_th copy of x then print say -1. Will binary search work ? Last edit: 2019-06-29 08:16:07 |
Added by: | BerSub |
Date: | 2016-09-21 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |