Upper bound
Dado um array de
n inteiros ordenados, é necessário responder a q consultas. Cada consulta pergunta: “Qual é o primeiro número que seja maior que x na lista fornecida?”.Entrada
A primeira linha da entrada contém dois inteiros
n (2 ≤ n ≤ ) e q (1 ≤ q ≤ ).A linha seguinte contém
n inteiros separados por espaço, ( ≤ ≤ ), em ordem crescente.A última linha contém
q consultas separadas por espaço, ( ≤ < ).Saída
O programa deve imprimir
q linhas. Cada linha conterá a resposta para a consulta correspondente.Exemplos
Entrada | Saída |
6 3
2 7 9 10 20 30
8 20 1 | 9
30
2 |
Dica
Na implementação clássica da pesquisa binária, considera-se o intervalo
[l; r), onde l é inclusivo e r é exclusivo. Em alguns casos, pode ser mais conveniente trabalhar com (l; r] — ou seja, excluir l e incluir r. Para isso, é preciso ajustar a forma de calcular l, r e mid.Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB