喷泉(Fountain)

题目描述

大家都知道喷泉吧？现在有一个喷泉由 $N$ 个圆盘组成，从上到下以此编号为 $1 \sim N$，第 $i$ 个圆盘的直径为 $D_i$，容量为 $C_i$，当一个圆盘里的水大于了这个圆盘的容量，那么水就会溢出往下流，直到流入半径大于这个圆盘的圆盘里。如果下面没有满足要求的圆盘，水就会流到喷泉下的水池里。

现在给定 $Q$ 组询问，每一组询问这么描述：

• 向第 $R_i$ 个圆盘里倒入 $V_i$ 的水，求水最后会流到哪一个圆盘停止。

如果最终流入了水池里，那么输出 $0$。

注意，每个询问互不影响。

输入格式

第一行两个整数 $N,Q$ 代表圆盘数和询问数。
接下来 $N$ 行每行两个整数 $D_i,C_i$ 代表一个圆盘。
接下来 $Q$ 行每行两个整数 $R_i,V_i$ 代表一个询问。

输出格式

$Q$ 行每行一个整数代表询问的答案。

样例输入 #1

6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8

样例输出 #1

5
0
5
4
2

数据范围

样例 1 解释

前两个询问的解释如下图所示：

因为每个询问互不影响，对于第三个询问，第 $5$ 个圆盘里的水不会溢出。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（30 pts）：$N \le 1000$，$Q \le 2000$。
• Subtask 2（30 pts）：$D_i$ 为严格单调递增序列。
• Subtask 3（40 pts）：无特殊限制。

对于 $100\%$ 的数据：

• $2 \le N \le 10^5$。
• $1 \le Q \le 2 \times 10^5$。
• $1 \le C_i \le 1000$。
• $1 \le D_i,V_i \le 10^9$。
• $1\le R_i \le N$。

说明

翻译自 eJOI 2020 Day1 A Fountain。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

测试点分布

出处：原题链接