## C - Counting 2 解説 by en_translator

If you naively compute the answer for each query, it will cost a complexity of $$O(QN)$$, which will exceed the time limit (TLE).

How can we find the answer of each query fast?

First of all, we sort $$N$$ people in the increasing order of their heights.

Given a sequence $$A$$ of length $$N$$ sorted in the increasing order and an integer $$x$$, we can use “binary search” to find the minimum $$i$$ such that $$x \leq A_i$$ in an $$O(\log N)$$ time. The following is a summary of binary search.

Suppose that we know that the desired $$i$$ is in the segment $$[l,r]$$ (initially $$l = 0, r = N$$).

Let $$md =\left\lfloor \dfrac{l + r}{2}\right\rfloor$$. If $$x \leq A_{md}$$, then we can determine that the desired $$i$$ is in the segment $$[l,md]$$; otherwise, it’s in the segment $$[md+1,r]$$.

For every step, the length of segment becomes half or less than the original one, so after a total of $$O(\log N)$$ steps, the length of the segment becomes $$1$$, and the desired $$i$$ can be found.

Note that many languages provide standard libraries of binary searching, which will simplify the implementation.

Sample code 1 (C++)

#include <bits/stdc++.h>
using namespace std;

int main(){
int n, q; cin >> n >> q;
vector<int> v(n);
for(int i = 0; i < n; i++) cin >> v[i];
sort(v.begin(),v.end());
for(int i = 0; i < q; i++){
int x; cin >> x;
int ok = n, ng = -1; // We know that v[ok] >= x, v[ng] < x
while(ok - ng > 1){
int md = (ok + ng) / 2;
if(v[md] >= x) ok = md;
else ng = md;
}
cout << n - ok << endl;
}
}


Sample code 2 (C++)

#include <bits/stdc++.h>
using namespace std;

int main(){
int n, q; cin >> n >> q;
vector<int> v(n);
for(int i = 0; i < n; i++) cin >> v[i];
sort(v.begin(),v.end());
for(int i = 0; i < q; i++){
int x; cin >> x;
cout << v.end() - lower_bound(v.begin(), v.end(), x) << endl;
}
}