Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 247 D問題 Cylinder

AtCoder ABC ABC247 D問題 400 pts

問題

提出解答

問題の概要

空の筒がある. 次の $Q$ 個のクエリを順に処理せよ.

(Type 1) $x$ と書かれたボールを $c$ 個筒の右から入れる.
(Type 2) 筒の左から $c$ のボールを取り出し, 取り出したボールに書かれている数の総和を求め, 出力する.

制約

$1 \leq Q \leq 2 \times 10^5$
$0 \leq x \leq 10^9$
$1 \leq c \leq 10^9$
(Type 2) において, 筒の中にあるボールの個数は $c$ 個以上

解法

筒の中にあるボールの個数は高々 $2 \times 10^{14}$ 個となり, そのまま管理はできない.

しかし, 整数はある程度固まっていることを利用し, 筒の中にあるボールを「 $x$ と書かれたボールが $c$ 個連なっている」というブロックで記録することにすると, 最大でも $Q$ 個のブロックになり, 管理できるようになる.

よって, 以下のアルゴリズム求めることができる.

$C$ を空の両側 Queue とする.
の順に以下を実行する.
- (Type 1) のとき: $C$ に $(x,c)$ を right enqueue する.
- (Type 2) のとき: とする.
  - である限り, 以下を実行する.
    - から deque し, を得たとする.
      - $d \leq c$ ならば, $c$ から $d$ を減らし, $a$ に $yd$ を加える.
      - $d \gt c$ ならば, $C$ に $(y,c-d)$ を left enqueue し, $a$ に $yc$ を加え, $c \gets 0$ とする.
  - $a$ を出力する.

これにより, 時間計算量 $O(Q)$ で処理することができた.