ABC 401-500/ABC413C - Large Queue - 競技プログラミング用 知識集積所

---

問題

ABC413C

必要知識

B以下レベルの内容は省略

• ランレングス圧縮※

考え方

問題の通りに整数列を作っていくと、10^14くらいのサイズの数列ができてアウト。
そこで、同じデータが連続することに注目し、ランレングス圧縮※を行う。

例えば入力例1なら、最初の2つのクエリで

3が2個、5が4個

という形でデータをもっておき、3つ目のクエリでは

3が2個、5が1個

を取り出して、数列には

5が3個

が残る……というようにデータを持つ。

vectorは前からの出し入れが苦手、queue※は余ったやつを先頭に戻せない。
よって、コンテナにはdeque※を使う必要がある。
（queue※でも、取り出さずに値の変更をすれば不可能ではないが……）

解答例

解答例

注意点

解答にはlong long型を用いる。

最終的な値はint型をはみ出る場合がある。

別解