22047번 - Dungeons Game 서브태스크다국어언어 제한함수 구현

문제

Robert is designing a new computer game. The game involves one hero, $n$ opponents and $n + 1$ dungeons. The opponents are numbered from 0ドル$ to $n - 1$ and the dungeons are numbered from 0ドル$ to $n$. Opponent $i$ (0ドル \le i \le n - 1$) is located in dungeon $i$ and has strength $s[i]$. There is no opponent in dungeon $n$.

The hero starts off entering dungeon $x,ドル with strength $z$. Every time the hero enters any dungeon $i$ (0ドル \le i \le n - 1$), they confront opponent $i,ドル and one of the following occurs:

• If the hero's strength is greater than or equal to the opponent's strength $s[i],ドル the hero wins. This causes the hero's strength to increase by $s[i]$ ($s[i] \ge 1$). In this case the hero enters dungeon $w[i]$ next ($w[i] > i$).
• Otherwise, the hero loses. This causes the hero's strength to increase by $p[i]$ ($p[i] \ge 1$). In this case the hero enters dungeon $l[i]$ next.

Note $p[i]$ may be less than, equal to, or greater than $s[i]$. Also, $l[i]$ may be less than, equal to, or greater than $i$. Regardless of the outcome of the confrontation, the opponent remains in dungeon $i$ and maintains strength $s[i]$.

The game ends when the hero enters dungeon $n$. One can show that the game ends after a finite number of confrontations, regardless of the hero's starting dungeon and strength.

Robert asked you to test his game by running $q$ simulations. For each simulation, Robert defines a starting dungeon $x$ and starting strength $z$. Your task is to find out, for each simulation, the hero's strength when the game ends.

구현

You should implement the following procedures:

void init(int n, int[] s, int[] p, int[] w, int[] l)

• $n$: number of opponents.
• $s,ドル $p,ドル $w,ドル $l$: arrays of length $n$. For 0ドル \le i \le n - 1$:
  • $s[i]$ is the strength of the opponent $i$. It is also the strength gained by the hero after winning against opponent $i$.
  • $p[i]$ is the strength gained by the hero after losing against opponent $i$.
  • $w[i]$ is the dungeon the hero enters after winning against opponent $i$.
  • $l[i]$ is the dungeon the hero enters after losing against opponent $i$.
• This procedure is called exactly once, before any calls to simulate (see below).

int64 simulate(int x, int z)

• $x$: the dungeon the hero enters first.
• $z$: the hero's starting strength.
• This procedure should return the hero's strength when the game ends, assuming the hero starts the game by entering dungeon $x,ドル having strength $z$.
• The procedure is called exactly $q$ times.

예제

Consider the following call:

init(3, [2, 6, 9], [3, 1, 2], [2, 2, 3], [1, 0, 1])

The diagram above illustrates this call. Each square shows a dungeon. For dungeons 0ドル,ドル 1ドル$ and 2ドル,ドル the values $s[i]$ and $p[i]$ are indicated inside the squares. Magenta arrows indicate where the hero moves after winning a confrontation, while black arrows indicate where the hero moves after losing.

Let's say the grader calls simulate(0, 1).

The game proceeds as follows:

As such, the procedure should return 24ドル$.

Let's say the grader calls simulate(2, 3).

The game proceeds as follows:

As such, the procedure should return 25ドル$.

입력

출력

제한

• 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$

서브태스크

힌트

샘플 그레이더

The sample grader reads the input in the following format:

• line 1ドル$: $n$ $q$
• line 2ドル$: $s[0]$ $s[1]$ $\cdots$ $s[n - 1]$
• line 3ドル$: $p[0]$ $p[1]$ $\cdots$ $p[n - 1]$
• line 4ドル$: $w[0]$ $w[1]$ $\cdots$ $w[n - 1]$
• line 5ドル$: $l[0]$ $l[1]$ $\cdots$ $l[n - 1]$
• line 6ドル + i$ (0ドル \le i \le q - 1$): $x$ $z$ for the $i$-th call to simulate.

The sample grader prints your answers in the following format:

• line 1ドル + i$ (0ドル \le i \le q - 1$): the return value of the $i$-th call to simulate.

첨부

• dungeons.zip