Intervals

A closed interval [a..b] contains the integers a, a+1, a+2, ... b-2, b-1, b. You are given N closed intervals [ai..bi] (0 ≤ N ≤ 100000), with ai and bi in the range [-109..109], and Q (0 ≤ Q ≤ 100000) queries of the form "how many intervals contain this integer x?" (where -2 × 109x ≤ 2 × 109). Determine the answer to each query.

Input Format
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 Format
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, ai and bi will be in the range [-1000..1000].

All Submissions
Best Solutions


Point Value: 10 (partial)
Time Limit: 5.00s
Memory Limit: 16M
Added: Dec 05, 2008
Author: bbi5291

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Between each pair of numerically adjacent endpoints (where an endpoint is either an a_i or a b_i value) there exists a region in which the answer to a query remains constant. There can be at max 2N+1 such regions. How can you precompute and efficiently retrieve the answers to queries then?


Sorry about that, it is 0 <= Q <= 100000.