複数クエリの境界探索 Bash(Beta)編（paizaランク A 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

ある駅の発車時刻表を管理するシステムを作っています。この駅では 1 日に N 本の電車が発車し、i 番目に発車する電車の時刻は A_i です（時刻は整数値で表します）。発車時刻は早い順に昇順に並んでいます（A_1 ≦ A_2 ≦ ... ≦ A_N）。Q 件の問い合わせ時刻 X_1, X_2, ..., X_Q が与えられます。各問い合わせ X_q（q = 1, 2, ..., Q）について、「時刻 X_q 以降に発車する最初の電車は何本目か」、つまり A_i ≧ X_q を満たす最小の i（先頭を 1 番目とする）を出力してください。そのような電車が存在しない場合は N + 1 を出力してください。

各クエリは二分探索で解いてください。

入力される値

入力は以下のフォーマットで与えられます。

N Q
A_1 A_2 ... A_N
X_1
X_2
...
X_Q

・1 行目には整数 N と整数 Q が空白区切りで与えられます。

・2 行目には N 個の整数 A_1, A_2, ..., A_N が空白区切りで与えられます。A は昇順に並んでいます。

・3 行目以降の Q 行には、各クエリの整数 X_q が 1 行ずつ与えられます。

・入力は合計で 2 + Q 行からなり、入力値最終行の末尾に改行が 1 つ入ります。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 各問い合わせについて、その時刻以降に発車する最初の電車が何本目か（先頭を 1 番目とする）を、それぞれ 1 行ずつ Q 行にわたって出力してください。存在しない場合は N + 1 を出力してください。出力の最後は改行し、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ N ≦ 10000

・1 ≦ Q ≦ 10000

・1 ≦ A_i ≦ 1000000000

・1 ≦ X_q ≦ 1000000000

・A は昇順に並んでいる（A_1 ≦ A_2 ≦ ... ≦ A_N）

入力例1: 5 3
10 20 30 40 50
25
50
100

出力例1: 3
5
6

入力例2: 4 3
5 15 25 35
3
15
40

出力例2: 1
2
5

問題一覧へ戻る