No.2861 Slime Party
タグ : / 解いたユーザー数 9
作問者 :
Problem Statement
$N$ slimes are lined up in a row on a number line, numbered from $1$ to $N$.
Slime $i$ is at coordinate $i$ and has level $A_i$. When you defeat it, your level increases by $X_i$ and the slime disappears. Here, the levels $A_i$ of the slimes are all distinct.
Initially, you are at coordinate $k + 0.5$ and your level is $L$.
You may then freely perform the following actions.- Letting $x$ be your current coordinate, move to coordinate $x - 1$. This action can be performed only if there is no slime between coordinates $x - 1$ and $x$.
- Letting $x$ be your current coordinate, move to coordinate $x + 1$. This action can be performed only if there is no slime between coordinates $x$ and $x + 1$.
- Letting $x$ be your current coordinate, defeat the slime at coordinate $x - 0.5$ if there is one. This action can be performed only if that slime's level is strictly lower than your level.
- Letting $x$ be your current coordinate, defeat the slime at coordinate $x + 0.5$ if there is one. This action can be performed only if that slime's level is strictly lower than your level.
You are given $Q$ queries. Process them in order.
Each query is of one of the following $2$ types.
1 a b: Change the amount by which your level increases when defeating slime $a$ to $b$. That is, set $X_a = b$.2 c: For the case $k = c$, output the maximum level you can achieve.
Constraints
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq Q \leq 2 \times 10^5$
- $1 \leq L \leq 10^{15}$
- $1 \leq A_i \leq 10^{15}$
- $1 \leq X_i \leq 10^9$
- $1 \leq a \leq N$
- $1 \leq b \leq 10^9$
- $1 \leq c \leq N - 1$
- All $A_i$ are distinct.
- All input values are integers.
Input
The input is given from standard input in the following format.
$N$ $Q$ $L$
$A_1$ $A_2$ ... $A_{N}$
$X_1$ $X_2$ ... $X_{N}$
query $1$
query $2$
$\vdots$
query $Q$
Each query is given in one of the following $2$ formats.
$1$ $a$ $b$
$2$ $c$
Output
Let $q$ be the number of queries of type $2$. Output $q$ lines.
On the $j$-th line $(1 \leq j \leq q)$, output the answer to the $j$-th such query.
Sample
Sample 1
Input
5 6 50 30 55 20 65 40 10 5 5 20 10 2 1 2 2 2 3 2 4 1 3 10 2 3
Output
100 55 55 60 105
For the $1$st query, you can achieve level $100$ by acting as follows.
- Defeat the slime at coordinate $1$. Your level becomes $60$.
- Defeat the slime at coordinate $2$. Your level becomes $65$.
- Move to coordinate $2.5$.
- Defeat the slime at coordinate $3$. Your level becomes $70$.
- Move to coordinate $3.5$.
- Defeat the slime at coordinate $4$. Your level becomes $90$.
- Move to coordinate $4.5$.
- Defeat the slime at coordinate $5$. Your level becomes $100$.
For the $2$nd query, you can achieve level $55$ by acting as follows.
- Defeat the slime at coordinate $3$. Your level becomes $55$.
For the $5$th query, the amount by which your level increases when defeating slime $3$ is changed to $10$.
For the $6$th query, you can achieve level $105$ by acting as follows.
- Defeat the slime at coordinate $3$. Your level becomes $60$.
- Defeat the slime at coordinate $2$. Your level becomes $65$.
- Move to coordinate $1.5$.
- Defeat the slime at coordinate $1$. Your level becomes $75$.
- Move to coordinate $2.5$.
- Move to coordinate $3.5$.
- Defeat the slime at coordinate $4$. Your level becomes $95$.
- Move to coordinate $4.5$.
- Defeat the slime at coordinate $5$. Your level becomes $105$.
Note that you cannot defeat a slime whose level is equal to yours.
Sample 2
Input
4 9 47 69 60 3 46 7 1 8 3 2 1 2 3 2 2 1 3 1 1 1 15 2 2 1 1 13 2 1 1 1 3
Output
47 58 58 51 47
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。