Upper bound
Data una lista ordinata di
n interi, devi rispondere a q interrogazioni (queries). Ogni query chiede: “Qual è il primo numero maggiore di x nella lista?”.Input
La prima riga dell’input contiene due interi
n (2 ≤ n ≤ ) e q (1 ≤ q ≤ ).La riga successiva contiene
n interi separati da spazio, ( ≤ ≤ ), in ordine crescente.L’ultima riga contiene
q interrogazioni separate da spazio, ( ≤ < ).Output
Il programma deve stampare
q righe. Ogni riga contiene la risposta per la query corrispondente.Esempi
Ingresso | Uscita |
6 3
2 7 9 10 20 30
8 20 1 | 9
30
2 |
Suggerimento
Nell’implementazione classica della ricerca binaria (binary search), spesso si considera l’intervallo
[l; r) in cui l è inclusivo e r non lo è. In alcuni casi, potresti preferire (l; r] – escludendo l e includendo r. Ciò richiede alcune modifiche nelle modalità di calcolo di l, r e mid.Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB