Time Limit: 2 second(s) | Memory Limit: 32 MB |
Given n points (1 dimensional) and q segments, you have to find the number of points that lie in each of the segments. A point p_{i} will lie in a segment A B if A ≤ p_{i} ≤ B.
For example if the points are 1, 4, 6, 8, 10. And the segment is 0 to 5. Then there are 2 points that lie in the segment.
Input starts with an integer T (≤ 5), denoting the number of test cases.
Each case starts with a line containing two integers n (1 ≤ n ≤ 10^{5}) and q (1 ≤ q ≤ 50000). The next line contains n space separated integers denoting the points in ascending order. All the integers are distinct and each of them range in [0, 10^{8}].
Each of the next q lines contains two integers A_{k} B_{k} (0 ≤ A_{k} ≤ B_{k} ≤ 10^{8}) denoting a segment.
For each case, print the case number in a single line. Then for each segment, print the number of points that lie in that segment.
Sample Input |
Output for Sample Input |
1 5 3 1 4 6 8 10 0 5 6 10 7 100000 |
Case 1: 2 3 2 |
Dataset is huge, use faster I/O methods.
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |