Counting Haybales (Editorial)

Sort the coordinates of the haybales.

Let $f(x)$ be the number of haybales in the interval $[0;x]$. Then, the number of haybales in the interval $[a;b]$ is equal to f(b) - f(a - 1).

Find the value of $f(x)$ using binary search.

Algorithm implementation

Read the input data.

scanf("%d %d", &n, &q);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Sort the coordinates of the haybales.

sort(v.begin(), v.end());

Process $q$ queries.

for (i = 0; i < q; i++)
{

Find and print the number of haybales $res$ in the interval from $a$ to $b$, inclusive.

  scanf("%d %d", &a, &b);
  res = upper_bound(v.begin(), v.end(), b) – 
        upper_bound(v.begin(), v.end(), a - 1);
  printf("%d\n", res);
}

Python implementation

import bisect

Read the input data.

n, q = map(int, input().split())
v = list(map(int, input().split()))

Sort the coordinates of the haybales.

v.sort()

Process $q$ queries.

for _ in range(q):

Find and print the number of haybales $res$ in the interval from $a$ to $b$, inclusive.

  a, b = map(int, input().split())
  res = bisect.bisect_right(v, b) - bisect.bisect_right(v, a - 1)
  print(res)