【UNR #4】己酸集合 - 题目 - Universal Online Judge

出题人 02 喜欢研究己酸 $(C H_{3} (C H_{2})_{4} C O O H)$ 的化学性质。

现在平面上有 $n$ 个己酸分子，第 $i$ 个分子位于 $(x_{i}, y_{i})$ 。己酸分子非常小，因此出题人 02 将其设为了一个点。

出题人 02 总是在想把这些己酸集合在一起会发生什么。所以他会问你 $Q$ 个问题：第 $i$ 个问题中，他想统计出到 $(0, z_{i})$ 这一点的欧几里得距离不超过 $R_{i}$ （小于等于 $R_{i}$ ）的己酸分子个数。

你作为未来的大理论计算机科学家，当然知道用什么算法和数据结构来解决啦！

第一行两个整数 $n, Q$ .

接下来 $n$ 行，每行两个整数 $x_{i}, y_{i}$ 。

接下来 $Q$ 行，每行两个整数 $z_{i}, R_{i}$ 。

$Q$ 行，第 $i$ 行一个整数表示第 $i$ 次询问的答案。

样例解释

~~这个样例是随机生成的，所以看上去非常不靠谱。~~

见样例数据下载。

该样例数据范围同测试包 1。

见样例数据下载。

该样例数据满足 $x_{i}, y_{i}, z_{i}$ 均在 $[- 10^{5}, 10^{5}]$ 均匀随机生成， $R_{i}$ 在 $[1, 10^{5}]$ 均匀随机生成。

测试包编号	$n$	$Q$	分值
$1$	$\leq 2000$	$\leq 5000$	$15$
$2$	$\leq 12000$	$\leq 5 \times 10^{5}$	$30$
$3$	$\leq 4000$	$\leq 10^{6}$	$20$
$4$	$\leq 7000$		$20$
$5$	$\leq 12000$		$15$

对于所有测试数据，满足 $1 \leq n \leq 12000, 0 \leq Q \leq 10^{6}, | x_{i} |, | y_{i} |, | z_{i} | \leq 10^{9}, 1 \leq R_{i} \leq 10^{9}$ 。

特殊地，测试包 2 中 $x_{i}, y_{i}, z_{i}, R_{i}$ 均是在上述合法范围内均匀随机生成的。

极限数据输入约 $21MB$ ，输出约 $5MB$ ，请选手注意自己 IO 的用时。

时间限制： $4 s$

空间限制： $512 MB$

Universal Online Judge