CF1651F Tower Defense

Monocarp 正在玩一款塔防游戏。游戏中的一个关卡可以表示为一条 OX 轴，其中每个从 $1$ 到 $n$ 的整数点上都有一个塔。 第 $i$ 个点上的塔有 $c_i$ 的魔力上限和 $r_i$ 的魔力恢复速度。一开始，在第 $0$ 秒之前，每个塔的魔力都是满的。如果在某一秒结束时，第 $i$ 个塔的魔力为 $x$，那么下一秒开始时它的魔力会变为 $\min(x + r_i, c_i)$。 关卡中会有 $q$ 只怪物出现。第 $j$ 只怪物会在第 $t_j$ 秒开始时出现在第 $1$ 个点，并且它有 $h_j$ 的生命值。每只怪物每秒会向坐标增大的方向移动 $1$ 个点。 当怪物经过某个塔时，该塔会对怪物造成 $\min(H, M)$ 的伤害，其中 $H$ 是怪物当前的生命值，$M$ 是塔当前的魔力。这个数值会同时从怪物的生命值和塔的魔力中扣除。 不幸的是，有时一些怪物可能会在通过所有 $n$ 个塔后依然存活。Monocarp 想知道，所有怪物通过所有塔后剩余的生命值总和是多少。

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示塔的数量。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $c_i$ 和 $r_i$（$1 \le r_i \le c_i \le 10^9$），分别表示第 $i$ 个塔的魔力上限和魔力恢复速度。 接下来一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示怪物的数量。 接下来的 $q$ 行中，第 $j$ 行包含两个整数 $t_j$ 和 $h_j$（$0 \le t_j \le 2 \cdot 10^5$；$1 \le h_j \le 10^{12}$），分别表示第 $j$ 只怪物出现的时间和它的生命值。 怪物按照出现时间递增的顺序给出，即对于所有 $1 \le j \le q-1$，都有 $t_j < t_{j+1}$。

输出一个整数，表示所有怪物通过所有塔后剩余的生命值总和。

由 ChatGPT 4.1 翻译