P16034 [CSPro 33] Ten Drops of Water

Luogu’s testdata is for community exchange only and is not official testdata. Official judging link: .

Ten Drops of Water is a very classic mini game. :::align{center}  ::: Player C is playing a one-dimensional version of the Ten Drops of Water game. We describe the basic rules of the game with an example. The game is played on a $1 \times c$ grid. Cells are indexed by integers $x\ (1 \le x \le c)$, increasing from left to right. Among the $c$ cells, $m$ cells contain $1 \sim 4$ drops of water, and the other cells contain no water. In our example, $c = m = 5$, and in index order, the numbers of drops in each cell are $2, 4, 4, 4, 2$. The player can perform several operations. In each operation, the player chooses a cell that contains water and increases the number of drops in that cell by $1$. At any time, if the number of drops in a cell is greater than or equal to $5$, the drops in this cell will burst to both sides. At this moment, the cell is cleared (its water becomes $0$). Then, for both the left and right directions, do the following at the same time: find the nearest cell in that direction that currently contains water; if such a cell exists, increase its number of drops by $1$. **If at some moment multiple cells have at least $5$ drops, the leftmost one bursts first.** In our example, if the player performs an operation on the third cell, its number of drops becomes $5$, so the third cell bursts. It is cleared, and the nearest cell with water on its left (the second cell) and on its right (the fourth cell) each gains $1$ drop. Now the numbers of drops become $2, 5, 0, 5, 2$. At this time, both the second and fourth cells have at least $5$ drops. According to the rule, the second cell bursts first. After that, the numbers of drops become $3, 0, 0, 6, 2$. Finally, the fourth cell bursts, and the numbers of drops become $4, 0, 0, 0, 3$. Player C has started a game and performed $n$ operations. After each operation, Player C will wait until all cells with at least $5$ drops have finished bursting before performing the next operation. Player C wants to know how good he is, so he wants to know how many cells still contain water after each operation. It is guaranteed that these $n$ operations are all valid, i.e., in each operation, the chosen cell contains water at that time.

Read from standard input. The first line contains three integers $c, m, n$, representing the grid width, the number of cells that contain water, and the number of operations. The next $m$ lines each contain two integers $x, w$, meaning that cell $x$ contains $w$ drops of water. The next $n$ lines each contain one integer $p$, meaning that Player C performs an operation on cell $p$.

Write to standard output. Output $n$ lines, each containing one integer: the number of cells that contain water after this operation.

### Subtasks For all testdata, - $1 \le c \le 10^9$，$1 \le m \le \min(c, 3 \times 10^5)$，$1 \le n \le 4m$； - $1 \le x, p \le c$，$1 \le w \le 4$； - All input $x$ are pairwise distinct； - For each input $p$, it is guaranteed that cell $p$ contains water at the time of the corresponding operation. | Subtask ID | $c \le$ | $m \le$ | Special Property | Score | |:----------:|:--------------:|:----------------:|:-----------------------------------------------------------------------:|:-----:| | 1 | $30$ | $30$ | Yes | 15 | | 2 | $3,000$ | $3,000$ | ^ | ^ | | 3 | ^ | ^ | No | 10 | | 4 | $10^9$ | ^ | ^ | 15 | | 5 | $3 \times 10^5$ | $3 \times 10^5$ | ^ | ^ | | 6 | $10^9$ | ^ | Yes | ^ | | 7 | ^ | ^ | No | ^ | Special Property: At any moment in the game (including during the chain reaction of bursting), there is at most one cell whose number of drops is greater than or equal to $5$. Translated by ChatGPT 5