B - Champagne Tower Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は、パーティーの準備としてシャンパンタワーを作ることになりました。シャンパンタワーといっても、今回は N 個のグラスを上から下へ一列に並べたシンプルな構造です。上から順に 1 段目、2 段目、\ldots、N 段目とします。

上から i 段目のグラスの容量は C_i ミリリットルです。

最初、すべてのグラスは空です。高橋君は Q 回の操作を順番に行います。各操作は以下の 2 種類のいずれかです：

  • 操作 1（注ぐ）：1 段目のグラスに V ミリリットルのシャンパンを注ぐ。注がれたシャンパンは 1 段目のグラスの現在のシャンパン量に加えられる。その結果、i 段目（1 \leq i \leq N-1）のグラスに入っているシャンパンの量が容量 C_i を超えている（容量より真に大きい）場合、超過分はすべて即座に i + 1 段目のグラスに流れ落ちる。この判定は 1 段目から順に各段について連鎖的に行われ、すべての段の処理が瞬時に完了する。最下段（N 段目）のグラスから溢れたシャンパンは失われ、どこにも溜まらない。操作完了時には各グラスのシャンパン量が容量以下に確定している。
  • 操作 2（問い合わせ）：k 段目のグラスに現在入っているシャンパンの量（ミリリットル）を出力する。

各操作 2 に対して、答えを出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq C_i \leq 10^9（1 \leq i \leq N）
  • 操作 1 において、1 \leq V \leq 10^9
  • 操作 2 において、1 \leq k \leq N
  • 操作 2 は 1 回以上与えられる
  • 入力はすべて整数である

入力

N Q
C_1 C_2 \ldots C_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
  • 1 行目には、グラスの段数を表す整数 N と、操作の回数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、上から i 段目のグラスの容量を表す整数 C_1, C_2, \ldots, C_N が、スペース区切りで与えられる。
  • 続く Q 行にわたって、各操作が 1 行ずつ与えられる。
  • 操作 1 の場合：1 V と与えられる。1 段目のグラスに V ミリリットルのシャンパンを注ぐことを意味する。V は正の整数である。
  • 操作 2 の場合：2 k と与えられる。k 段目のグラスに現在入っているシャンパンの量を問い合わせることを意味する。k は 1 以上 N 以下の整数である。

出力

操作 2 が与えられるたびに、指定された k 段目のグラスに現在入っているシャンパンの量（ミリリットル）を 1 行に 1 つずつ出力せよ。なお、入力がすべて整数であることから、答えは必ず整数となる。

入力例 1

3 7
5 3 4
2 1
1 4
2 1
1 3
2 1
2 2
2 3

出力例 1

0
4
5
2
0

入力例 2

4 8
2 2 2 2
1 1
2 1
1 10
2 1
2 2
2 3
2 4
2 4

出力例 2

1
2
2
2
2
2

入力例 3

8 15
3 7 2 10 5 1 8 6
2 5
1 4
2 1
2 2
1 20
2 1
2 2
2 3
2 4
1 6
2 4
2 5
1 15
2 7
2 8

出力例 3

0
3
1
3
7
2
10
10
5
8
6

入力例 4

25 40
100 1 50 200 3 400 5 600 7 800 9 1000 11 1200 13 1400 15 1600 17 1800 19 2000 21 2200 23
1 75
2 1
2 2
1 1000
2 1
2 3
2 4
1 5000
2 5
2 8
2 10
1 12345
2 12
2 15
2 20
1 999999999
2 1
2 2
2 3
2 10
2 25
1 1
2 25
1 2500
2 6
2 7
2 11
2 13
1 777
2 14
2 16
2 18
1 424242
2 19
2 21
2 22
2 23
2 24
1 314159265
2 25

出力例 4

75
0
100
50
200
3
600
800
1000
13
1800
100
1
50
800
23
23
400
5
9
11
1200
1400
1600
17
19
2000
21
2200
23

入力例 5

1 7
1000000000
2 1
1 1
2 1
1 999999999
2 1
1 1000000000
2 1

出力例 5

0
1
1000000000
1000000000

Score : 333 pts

Problem Statement

Takahashi is preparing a champagne tower for a party. However, this time it is a simple structure with N glasses arranged in a single column from top to bottom. The glasses are numbered from the top as level 1, level 2, \ldots, level N.

The capacity of the glass at level i from the top is C_i milliliters.

Initially, all glasses are empty. Takahashi performs Q operations in order. Each operation is one of the following two types:

  • Operation 1 (pour): Pour V milliliters of champagne into the glass at level 1. The poured champagne is added to the current amount of champagne in the level 1 glass. As a result, if the amount of champagne in the glass at level i (1 \leq i \leq N-1) exceeds its capacity C_i (is strictly greater than the capacity), all the excess immediately flows down to the glass at level i + 1. This check is performed sequentially from level 1 in a cascading manner, and all processing is completed instantaneously. Champagne that overflows from the bottom glass (level N) is lost and does not accumulate anywhere. Upon completion of the operation, the amount of champagne in each glass is guaranteed to be at most its capacity.
  • Operation 2 (query): Output the amount of champagne (in milliliters) currently in the glass at level k.

For each operation 2, output the answer.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
  • For operation 1: 1 \leq V \leq 10^9
  • For operation 2: 1 \leq k \leq N
  • Operation 2 is given at least once
  • All input values are integers

Input

N Q
C_1 C_2 \ldots C_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
  • The first line contains an integer N representing the number of glass levels and an integer Q representing the number of operations, separated by a space.
  • The second line contains integers C_1, C_2, \ldots, C_N representing the capacity of the glass at level i from the top, separated by spaces.
  • The following Q lines each contain one operation.
  • For operation 1: Given as 1 V. This means pouring V milliliters of champagne into the glass at level 1. V is a positive integer.
  • For operation 2: Given as 2 k. This means querying the amount of champagne currently in the glass at level k. k is an integer between 1 and N, inclusive.

Output

Each time operation 2 is given, output the amount of champagne (in milliliters) currently in the specified glass at level k, one per line. Since all input values are integers, the answer is always an integer.

Sample Input 1

3 7
5 3 4
2 1
1 4
2 1
1 3
2 1
2 2
2 3

Sample Output 1

0
4
5
2
0

Sample Input 2

4 8
2 2 2 2
1 1
2 1
1 10
2 1
2 2
2 3
2 4
2 4

Sample Output 2

1
2
2
2
2
2

Sample Input 3

8 15
3 7 2 10 5 1 8 6
2 5
1 4
2 1
2 2
1 20
2 1
2 2
2 3
2 4
1 6
2 4
2 5
1 15
2 7
2 8

Sample Output 3

0
3
1
3
7
2
10
10
5
8
6

Sample Input 4

25 40
100 1 50 200 3 400 5 600 7 800 9 1000 11 1200 13 1400 15 1600 17 1800 19 2000 21 2200 23
1 75
2 1
2 2
1 1000
2 1
2 3
2 4
1 5000
2 5
2 8
2 10
1 12345
2 12
2 15
2 20
1 999999999
2 1
2 2
2 3
2 10
2 25
1 1
2 25
1 2500
2 6
2 7
2 11
2 13
1 777
2 14
2 16
2 18
1 424242
2 19
2 21
2 22
2 23
2 24
1 314159265
2 25

Sample Output 4

75
0
100
50
200
3
600
800
1000
13
1800
100
1
50
800
23
23
400
5
9
11
1200
1400
1600
17
19
2000
21
2200
23

Sample Input 5

1 7
1000000000
2 1
1 1
2 1
1 999999999
2 1
1 1000000000
2 1

Sample Output 5

0
1
1000000000
1000000000