P8522 [IOI 2021] Dungeon Game

**Abusing the judging system for this problem will result in your account being banned.** **Due to technical limitations, please do not submit this problem using C++ 14 (GCC 9).** This is an interactive problem. You only need to implement the functions required in the code. Your code does not need to include any additional header files, and you do not need to implement the `main` function.

Robert is designing a new computer game. In the game, there is one hero, $n$ enemies, and $n + 1$ dungeons. The enemies are numbered from $0$ to $n - 1$, and the dungeons are numbered from $0$ to $n$. Enemy $i$ ($0 \le i \le n - 1$) is located in dungeon $i$, and has strength $s[i]$. Dungeon $n$ has no enemy. The hero initially enters dungeon $x$ with initial strength $z$. Each time the hero enters dungeon $i$ ($0 \le i \le n - 1$), they must face enemy $i$, and one of the following happens: - If the hero's strength is greater than or equal to the enemy $i$'s strength $s[i]$, then the hero wins. This increases the hero's strength by $s[i]$ ($s[i] \ge 1$). In this case, the hero will next enter dungeon $w[i]$ ($w[i] > i$). - Otherwise, the hero loses. This increases the hero's strength by $p[i]$ ($p[i] \ge 1$). In this case, the hero will next enter dungeon $l[i]$. Note that $p[i]$ may be less than, equal to, or greater than $s[i]$, and $l[i]$ may be less than, equal to, or greater than $i$. Regardless of the battle result, enemy $i$ always stays in dungeon $i$ and its strength remains $s[i]$. When the hero enters dungeon $n$, the game ends. It can be seen that no matter what the hero's starting dungeon and initial strength are, the game will always end after a finite number of battles. Robert wants you to test the game using $q$ simulations. For each simulation, Robert provides the hero's starting dungeon $x$ and initial strength $z$. You need to output the hero's strength when the game ends for each simulation.

You need to implement the following functions: ```cpp void init(int n, int[] s, int[] p, int[] w, int[] l) ``` - $n$: the number of enemies. - $s$, $p$, $w$, $l$: sequences of length $n$. For each $i$ ($0 \le i \le n - 1$): + $s[i]$ is the strength of enemy $i$, and also the amount by which the hero's strength increases after defeating enemy $i$. + $p[i]$ is the amount by which the hero's strength increases after being defeated by enemy $i$. + $w[i]$ is the index of the next dungeon the hero enters after defeating enemy $i$. + $l[i]$ is the index of the next dungeon the hero enters after being defeated by enemy $i$. - This function is called exactly once, and it is called before any calls to the following `simulate` function. ```cpp int64 simulate(int x, int z) ``` - $x$: the index of the hero's starting dungeon. - $z$: the hero's initial strength. - Assuming the hero starts in dungeon $x$ with initial strength $z$, the return value is the hero's strength when the game ends in that case. - This function is called exactly $q$ times.

N/A

For all testdata: - $1 \le n \le 400 \, 000$ - $1 \le q \le 50 \, 000$ - $1 \le s[i], p[i] \le {10}^7$（for all $0 \le i \le n - 1$） - $0 \le l[i], w[i] \le n$（for all $0 \le i \le n - 1$） - $w[i] > i$（for all $0 \le i \le n - 1$） - $0 \le x \le n - 1$ - $1 \le z \le {10}^7$ Subtasks | Score | Special Constraints :-:|:-:|:-: $0$ | $0$ | Sample. $1$ | $11$ | $n \le 50 \, 000$, $q \le 100$, $s[i], p[i] \le 10 \, 000$ (for all $0 \le i \le n - 1$). $2$ | $26$ | $s[i] = p[i]$ (for all $0 \le i \le n - 1$). $3$ | $13$ | $n \le 50 \, 000$, all enemies have the same strength, i.e., $s[i] = s[j]$ for all $0 \le i, j \le n - 1$. $4$ | $12$ | $n \le 50 \, 000$, there are at most $5$ distinct values among all $s[i]$. $5$ | $27$ | $n \le 50 \, 000$. $6$ | $11$ | No additional constraints. Translated by ChatGPT 5