## C - Counting 2 Editorial 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;
}
}
```

posted:

last update: