座標圧縮
(paizaランク B 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
横一直線に並んだ 1,000,000,000 (= 10^9 ) 個のマスがあり、左から A_1, ..., A_N 番目の N 個のマスに色を塗りました。全部で Q 回行われる以下の質問にすべて答えてください。
・左から X_i ( 1 ≦ i ≦ Q ) 番目のマスは色が塗られていることがわかりました。このマスは色が塗られているマスのうち左から何番目のマスでしょう。
- 入力される値
-
N Q
A_1 A_2 A_3 ... A_N
X_1 X_2 X_3 ... X_Q
・ 1 行目に、数値 N, Q が与えられます。
・ 2 行目に数列 A が与えられます。
・ 3 行目に数列 X が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
左から X_i 番目のマスは色が塗られているマスのうち左から何番目のマスか計算し、それらを改行区切りで出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 100,000
・ 1 ≦ Q ≦ 100,000
・ 1 ≦ A_i ≦ 1,000,000,000
・ A の中に重複する値はありません
・ 1 ≦ X_i ≦ 1,000,000,000
・ X_i は A に含まれる
- 入力例1
-
6 4
11 6 16 5 2 13
5 11 13 2
- 出力例1
-
2
4
5
1
