RCKCNT Editorial

editorial
1

Problem Explanation

We are given an array of samples and an R queries where each query consist of a range (L, R), we have to output how many samples lie in this range(inclusive).

Approach

To efficiently search through the array, we sort the array and apply binary search on the array for the Left and Right boundaries of the range. And output the difference of the position of Left and Right boundaries as all the elements in the between will lie in the range.

Code

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m, l, r;
    cin >> n >> m;
    vector < int > a(n), ans;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());
    while (m--)
    {
        int an = 0;
        cin >> l >> r;
        int temp = upper_bound(a.begin(), a.end(), r) - lower_bound(a.begin(), a.end(), l);
        ans.push_back(temp);
    }
    for (auto i: ans) cout << i << " ";
    cout<<endl;
}