主页 讨论版 问题 名次 状态 统计
12月将举办首届西电ACM新生赛,敬请期待~~~~
问题 E: Counting Stars

问题 E: Counting Stars

时间限制: 2 Sec  内存限制: 128 MB
提交: 154  解决: 42
[提交][状态][讨论版]

题目描述

   "But baby, I've been, I've been praying hard,
    Said, no more counting dollars
    We'll be counting stars"


Grandpa Shaw loves counting stars.
One evening he was sitting in his armchar, trying to figure out this problem.

Consider the sky as a rectangular coordinates, each star has a coordinate (Xi,Yi).
To make it simple, all the stars are in the first quadrant.
Now he want to know how many stars there are in the square formed by (0,0) and (x,y).
(including stars in edges, 4 vertices of the square is (0,0) (x,0) (x,y) (0,y))

There are n stars in the sky, and he raised m questions.
Because grandpa Shaw's eyesight is poor, he ask you for help.

[img]
in this image, yellow stars are in the square, blue ones are not.

输入

multiple test cases, please read until EOF.
for each test case:
first line contains two integers n m (0 <= n, m <= 10^5).
following n lines each line contains two integers Xi Yi (0 <= Xi, Yi <= 10^6).
following m lines each line contains two integers x y (0 <= x, y <= 10^6).

输出

for each test case:
first line "Case #t:" t is the number of test case.
following m lines, each line contains one integer, the number of stars in that square.

样例输入

7 2
0 23
20 31
44 18
50 43
40 77
67 0
84 40
67 43
99 99

样例输出

Case #1:
5
7

提示

first question of the test case is as the image shows.


input data is large, DO NOT use cin, use scanf instead.


测试数据保证星星的位置没有重合

[提交][状态][讨论版]