011 - Number-Collection
時間制限 0.5 秒 / メモリ制限 256 MB / 得点 15 / x 6 /
問題
YDKは $N$ 個の整数 $a_i$ をコレクションとして所持しています。
彼のコレクションは必ず $a_i$ ≤ $a_j$ ($i$ < $j$) となっています。
$Q$ 個の整数 $v_i$ が与えられるので、YDKが $v_i$ をいくつ所持しているか答えてください。
入出力
入力
1行目に、YDKが所持している整数の個数 $N$ が入力される。
2行目に、YDKが所持している $N$ 個の整数 $a_i$ が空白区切りで入力される。
続いて、$Q$ が一行に入力される。
以下、$Q$ 行にわたって $v_j$ が空白区切りで入力される。
N a1 a2 ... aN Q v1 v2 ... vQ
出力
各 $v_i$ について、YDKが $v_i$ を所持している個数を改行区切りで出力せよ。
制約
- 1 ≤ $N$ ≤ 3,000,000
- -1,000,000,000 ≤ $a_i$,$v_i$ ≤ 1,000,000,000
- 1 ≤ $Q$ ≤ 500,000
- $a_i$ ≤ $a_j$ ($i$ < $j$)
部分点
以下の各条件を満たすテストケースに正解すると、部分点がもらえる。
部分点a [配点の10%]
$N$, $Q$ ≤ 1000 を満たす。
部分点b [配点の10%]
0 ≤ $a_i$ ≤ 1,000,000 を満たす。
部分点c [配点の30%]
$a_i$ ≠ $a_j$ ($i$ ≠ $j$) を満たす。これは、$a_i$は重複しないという意味である。
部分点d [配点の100%]
追加の制約なし。
入出力例
入力例1
3 1 7 12 4 1 12 -1 6
出力例1
1 1 0 0
この例では、YDKは{ $1$, $7$, $12$ }の3数を所持している。
所持を判定する整数は4つあり、$1$は1個、$12$は1個、$-1$は0個、$6$は0個所持しているのでこのように出力する。
なお、これは部分点a,b,c,dのテストケースの一つである。
入力例2
7 -4 5 5 5 8 9 9 4 9 5 -1 10000000
出力例2
2 3 0 0
これは、部分点a,dのテストケースの一つである。
hoge
cin, cout は
cin.tie(0), ios::sync_with_stdio(false);がないとTLEします。
あと、 std::endl を使うと TLE するかもしれません(もしそうなったら cout << '\n' にしてください)。