10559. Counting haybales

 

Farmer John has placed his n haybales at different points along a one-dimensional road next to his farm. You need to answer q queries about how many haybales are located within a specified section of the road.

 

Input. The first line contains two integers n (1 ≤ n ≤ 105) and q (1 ≤ q ≤ 105).
The next line contains n distinct integers, each in the range 0 ... 109, representing the positions of the haybales.

Each of the following q lines contains two integers a and b (0 ≤ a ≤ b ≤ 109), specifying a query for the number of haybales between a and b, inclusive.

 

Output. Print q lines. For each query, print the number of haybales within the specified range on a separate line.

 

Sample input

Sample output

4 6

3 2 7 5

2 3

2 4

2 5

2 7

4 6

8 10

2

2

3

4

1

0

 

 

 

SOLUTION

binary search

 

Algorithm analysis

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)