Upper bound (上限)
ソート済みの
n 個の整数からなる配列が与えられたとき、q 件のクエリに答えることが求められます。各クエリの内容は「与えられたリストで、x よりも大きい最初の要素は何か？」というものです。入力
最初の行には、
n (2 ≤ n ≤ ) と q (1 ≤ q ≤ ) の 2 つの整数が与えられます。次の行には、昇順に並んだ
n 個の整数 ( ≤ ≤ ) が空白区切りで与えられます。最後の行には、
q 個のクエリ ( ≤ < ) が空白区切りで与えられます。出力
プログラムは
q 行を出力します。各行には、対応するクエリに対する答えを出力してください。例
入力 | 出力 |
6 3
2 7 9 10 20 30
8 20 1 | 9
30
2 |
Hint
古典的な二分探索の実装では、
[l; r) という範囲を用い、l は含み、r は含みません。しかし、場合によっては (l; r] のように l を除外し、r を含む形で実装したいこともあります。その場合、l、r、mid の計算方法を少し変更する必要があります。Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB