Cota superior
Dado un arreglo de
n enteros ordenados, se te pide responder q consultas. Cada consulta consiste en la pregunta: “¿Cuál es el primer número mayor que x en la lista dada?”.Entrada
La primera línea de la entrada contiene dos enteros
n (2 ≤ n ≤ ) y q (1 ≤ q ≤ ).La siguiente línea contiene
n enteros separados por espacios ( ≤ ≤ ) en orden ascendente.La última línea contiene
q consultas separadas por espacios ( ≤ < ).Salida
El programa debe imprimir
q líneas. En cada línea se mostrará la respuesta correspondiente a la consulta.Ejemplos
Entrada | Salida |
6 3
2 7 9 10 20 30
8 20 1 | 9
30
2 |
Hint
En la implementación clásica de la búsqueda binaria, se considera el rango
[l; r) donde l es inclusivo y r es exclusivo. En algunos casos, podría preferirse (l; r] en su lugar (excluir l e incluir r). Esto exigirá algunos cambios al calcular los valores de l, r y mid.Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB