B - Binary Search

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_B (新しいタブで開く)

問題文

$n$ 個の整数からなる数列 $S$、 $q$ 個の相異なる整数からなる数列 $T$ が与えられる。
$T$ に含まれる整数で $S$ に含まれるものの個数 $C$ は？

制約

• $n \le 100,000$
• $q \le 50,000$
• $0 \le S_i, T_i \le 10^9$
• $i \neq j \Rightarrow T_i \neq T_j$
• $i < j \Rightarrow S_i \le S_j$

サンプル

I/O 1

5
1 2 3 4 5
3
3 4 1

3

I/O 2

3
3 1 2
1
5

0

I/O 3

5
1 1 2 2 3
2
1 2

2

考察

$O(nq)$ が間に合わないけど、 $T$ が相異なるので「含まれるか」を判定できればいいので set を使う

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_4_B/judge/6312077/C++ (新しいタブで開く)

int main() {
  int n;
  cin >> n;
  set<int> s;
  rep(i, n) {
    int x;
    cin >> x;
    s.insert(x);
  }
  int q;
  cin >> q;
  int ans = 0;
  rep(i, q) {
    int x;
    cin >> x;
    if (s.count(x)) ++ans;
  }
  cout << ans << endl;
  return 0;
}