問題一覧 > 通常問題

No.2861 Slime Party

レベル : / AI推定難易度 : 2325 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 9
作問者 : dyktr_06 / テスター : square1001
お気に入りにしたユーザー ProblemId : 10929 / 自分の提出
問題文最終更新日: 2024-08-25 10:46:36
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 442 MMA Contest 019 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。