Intervals

View as PDF

Submit solution

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

Problem type

A closed interval [ab] contains the integers a,a+1,,b. You are given N closed intervals [aibi] (0N100000), with ai and bi in the range [109109], and Q (0Q100000) queries of the form "how many intervals contain this integer x?" (where 2×109x2×109). 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, ai and bi, 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

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

Sample Output

Copy
0
1
1
2
3
2
1
1
1
0

Note: In test cases worth 25% of the points, ai and bi will be in the range [10001000].


Comments

There are no comments at the moment.