Intervals

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.5s
Memory limit: 16M

Problem type

A closed interval [a \dots b] contains the integers a, a+1, \dots, b. You are given N closed intervals [a_i \dots b_i] (0 \le N \le 100\,000), with a_i and b_i in the range [-10^9 \dots 10^9], and Q (0 \le Q \le 100\,000) queries of the form "how many intervals contain this integer x?" (where -2 \times 10^9 \le x \le 2 \times 10^9). Determine the answer to each query.

Input Specification

Line 1: Two space-separated integers, N and Q.
Next N lines: Two space-separated integers each, a_i and b_i, denoting one closed interval.
Next Q lines: One integer each, denoting a single query.

Output Specification

Print the answer to each query on its own line.

Sample Input

3 10
0 3
2 4
3 7
-1
0
1
2
3
4
5
6
7
8

Sample Output

0
1
1
2
3
2
1
1
1
0

Note: In test cases worth 25\% of the points, a_i and b_i will be in the range [-1\,000 \dots 1\,000].


Comments

There are no comments at the moment.