How Many Intervals Cover X

Difficulty: 1400 3500 ms 128 MB

intervals prefix-sums

N intervals [L, R] over coordinates 1..10⁵ are given, then Q point queries: how many intervals contain the point X?

Input: the first line has N and Q; the next N lines have the intervals; the next Q lines each have one X.

Output: Q lines with the coverage counts.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• 1 ≤ L ≤ R ≤ 10⁵

Sample Tests

2 2
1 5
3 8
4
9

2
0

1 1
2 2
2

1

Read the Editorial