USACO 2016 December Contest Silver Division - Counting Haybales

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This is a standard binary search problem, where after sorting the input, all we have to do for each query is to find out how many numbers are smaller or equal than \(R\) and subtract from that answer how many numbers are smaller than \(L\). Both of these answers can be found easily using binary search on the sorted array.

Source code

The source code in C++ can be seen below.

#include <fstream>
#include <algorithm>
using namespace std;

int n, q, v[100002];

int solve(int x) {
    int ans = 0;
    int L = 0;
    int R = n;
    while (L <= R) {
        int mid = (L + R) / 2;
        if (v[mid] <= x)
            ans = mid, L = mid + 1;
        else
            R = mid - 1;
    }
    return ans;
}

int main() {
    ifstream cin("haybales.in");
    ofstream cout("haybales.out");

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    sort(v + 1, v + n + 1);

    for (; q; q--) {
        int L, R;
        cin >> L >> R;

        cout << solve(R) - solve(L - 1) << '\n';
    }
    return 0;
}