ABC 401-500/ABC443C - Chokutter Addiction - 競技プログラミング用 知識集積所

---

問題

ABC443C

必要知識

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

• 特になし

考え方

タイムラインをpriority_queue※で整理しながらシミュレーションを行えばよい。
すなわち、1を開く動作、0を閉じる動作、-1を終業として、「時刻、起こること」を時刻が速い順に見ていけばよい。

1のときには、今chokutterを開いていないなら、開く。
0のときや-1のときには、今chokutterを開いているなら、閉じて100秒後に開く予定を追加する。
さらに-1の場合は加えてシミュレーションを終了する。
これで、いつ開いていつ閉じるかが全てわかる。

あとは開いていた時間の計算。
連続して開いていた期間ごとに「閉じた時刻-開いた時刻」の計算をして合計していけばよい。
シミュレーションとは別に計算をしてもいいが、

• 開いた瞬間に現在時刻を引く
• 閉じた瞬間に現在時刻を足す

としてしまうと楽。

解答例

解答例

注意点

別解