Tower Defense
Contest: Educational Codeforces Round 124 (Rated for Div. 2)
Difficulty rating: 3000
Tags: binary search, brute force, data structures

Monocarp is playing a tower defense game. A level in the game can be represented as an OX axis, where each lattice point from $$$1$$$ to $$$n$$$ contains a tower in it.

The tower in the $$$i$$$-th point has $$$c_i$$$ mana capacity and $$$r_i$$$ mana regeneration rate. In the beginning, before the $$$0$$$-th second, each tower has full mana. If, at the end of some second, the $$$i$$$-th tower has $$$x$$$ mana, then it becomes $$$\mathit{min}(x + r_i, c_i)$$$ mana for the next second.

There are $$$q$$$ monsters spawning on a level. The $$$j$$$-th monster spawns at point $$$1$$$ at the beginning of $$$t_j$$$-th second, and it has $$$h_j$$$ health. Every monster is moving $$$1$$$ point per second in the direction of increasing coordinate.

When a monster passes the tower, the tower deals $$$\mathit{min}(H, M)$$$ damage to it, where $$$H$$$ is the current health of the monster and $$$M$$$ is the current mana amount of the tower. This amount gets subtracted from both monster's health and tower's mana.

Unfortunately, sometimes some monsters can pass all $$$n$$$ towers and remain alive. Monocarp wants to know what will be the total health of the monsters after they pass all towers.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of towers.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$c_i$$$ and $$$r_i$$$ ($$$1 \le r_i \le c_i \le 10^9$$$) — the mana capacity and the mana regeneration rate of the $$$i$$$-th tower.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of monsters.

The $$$j$$$-th of the next $$$q$$$ lines contains two integers $$$t_j$$$ and $$$h_j$$$ ($$$0 \le t_j \le 2 \cdot 10^5$$$; $$$1 \le h_j \le 10^{12}$$$) — the time the $$$j$$$-th monster spawns and its health.

The monsters are listed in the increasing order of their spawn time, so $$$t_j < t_{j+1}$$$ for all $$$1 \le j \le q-1$$$.

Output format:
Print a single integer — the total health of all monsters after they pass all towers.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example input:
3
5 1
7 4
4 2
4
0 14
1 10
3 16
10 16

Example output:
4

Example input:
5
2 1
4 1
5 4
7 5
8 3
9
1 21
2 18
3 14
4 24
5 8
6 25
7 19
8 24
9 24

Example output:
40

Editorial:
Let's start thinking about the problem from the easy cases.
How to solve the problem fast if all towers have full mana? We can store prefix sums of their capacities and find the first tower that doesn't get drained completely with a binary search.
Let's try the opposite. How to solve the problem fast if all towers were drained completely in the previous second? It's the same but the prefix sums are calculated over regeneration rates.
What if all towers were drained at the same second, earlier than the previous second, and no tower is fully restored yet? It's also the same but the regeneration rates are multiplied by the time passed since the drain.
What if we drop the condition about the towers not being fully restored? How would a data structure that can answer prefix sum queries work? It should store the total mana capacity of all towers that are full. Then mana regeneration rates for all towers that aren't. If these are kept separately, then it's easy to obtain the prefix sum by providing the time passed. This will be total capacity plus total regeneration rate, multiplied by the time passed.
How to determine if the tower is fully restored since the drain or not? That's easy. For each tower, we can calculate the number of seconds it takes it to get restored from zero. That is $$$\lceil \frac{c}{r} \rceil$$$. Thus, all towers that have this value smaller than the time passed won't get restored. All the rest will.
Unfortunately, in the actual problem, not all towers were last drained at the same time. However, it's possible to reduce the problem to that. Store the segments of towers that were drained at same time. There are also towers that weren't drained completely, but they can be stored as segments of length $$$1$$$ too. When a monster comes, it drains some prefix of the towers completely and possibly one more tower partially. In terms of segments, it removes some prefix of the them and possibly cuts one. Then it creates a segment that covers the prefix and possibly a segment of length $$$1$$$ (with a partially drained tower). So each monster creates $$$O(1)$$$ segments and removes no more segments than were created. Thus, if we were to process each creation and removal in some $$$O(T)$$$, then the complexity will be $$$O(qT)$$$.
All towers on each segment have the same time passed since the drain. We want to query the sum on the entire segment. If it is greater than the remaining health of the monster, we want to find the largest prefix of this segment that has a smaller or equal sum than the monster health.
Given time passed, let's learn to query the range sum. If we knew the queries beforehand, it would be easy. Initialize a segment tree as if all towers are completely restored. Then make events of two kinds: a tower with restore time $$$\lceil \frac{c}{r} \rceil$$$ and a query with time $$$t$$$. Sort them in the decreasing order and start processing one by one. When a tower event happens, update a single position in the segment tree from capacity to regeneration rate. When a query event happens, find the sum.
Since the queries are not known beforehand, make that segment tree persistent and ask specific versions of it. If a segment of towers was last drained at time $$$t_{\mathit{lst}}$$$, and the query is at time $$$t$$$, then you should query the segment tree in version $$$t - t_{\mathit{lst}}$$$. Obviously, you can store not all versions but only ones that have some tower change. Moreover, it's more convenient to make one version responsible for one tower update. Then you can lower_bound the array of sorted $$$\lceil \frac{c}{r} \rceil$$$ to find the version you want to ask at.
To determine the largest prefix of this segment that has a smaller or equal sum than the monster health, you can either binary search for $$$O(\log^2 n)$$$ or traverse the segment tree for $$$O(\log n)$$$. The time limit might be a little tight for the first approach, but it can still pass.
Overall complexity: $$$O((n + q) \log n)$$$.