AtCoder Beginner Contest 217 [ D - Cutting Woods ]をPythonで解く（400点、🟩緑diff）

問題

atcoder.jp

問題概要

長さLの木材がある．以下のQ個のクエリを処理せよ．
i番目のクエリは(ci,xi)で与えられる．

• ci=1のとき：木材の左端からxiの地点で木材を切る．
• ci=2のとき：木材の左端からxiの地点を含む木材の長さを出力する．

1≤L≤10⁹
1≤Q≤2×10⁵
ci=1,2
1≤xi≤L−1
(問題概要かんプリンさんサイトより引用)

解法

木の右端と左端の配列を作成（0, L）。
これに二分探索で要素を追加、二分探索で要素を検索を行う。

二分探索はpythonでお馴染みの、bisectを使うのだが、検索対象をlistではなくarrayにしているところがポイント。
listにした場合、PyPy7.3.0でTLEが1個出てしまって通らない。

これはlistへの要素追加が処理が重く、足を引っ張っている。
検索したところarrayへの要素追加は、listと比較して1/3の計算量で済むので、データ管理をarrayに変更することでACできた。

実装

参考

x1.inkenkun.com arrayにしたほうがlistより要素追加が軽いことが書いてある。

kanpurin.hatenablog.com

問題概要を引用させてもらいました。
ありがとうございます。