Binary Search 10816

1
// 18870
2

3
//10816  lower bound and upper bound
4
#include <bits/stdc++.h>
5

6
using namespace std;
7
int main()
8
{
9
    int n, m;
10
    cin >> n;
11

12
    vector<int>a(n);
13
    for(int i = 0; i < n; i++)
14
    {
15
        cin >> a[i];
16
    }
17

18
    cin >> m;
19
    vector<int>b(m);
20
    for(int i = 0; i < m; i++)
21
    {
22
        cin >> b[i];
23
    }
24

25
    sort(a.begin(), a.end());
26

27

28
    vector<int> count(m);
29

30
   for(int i = 0; i < m; i++)
31
   {
32
        int lower = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
33
        int upper = upper_bound(a.begin(), a.end(), b[i]) - a.begin();
34
        count[i] = upper - lower;
35

36
    }
37

38
    for(int i = 0; i < m; i++)
39
    {
40
        cout << count[i] << " ";
41
    }
42

43

44
    return 0;
45
   }