7K12 blog

猫でも分かるアルゴリズム解説

第9回日本情報オリンピック 本選 A - 旅人

f:id:tkr987:20200803065941p:plain

f:id:tkr987:20200803070058p:plain

https://atcoder.jp/contests/joi2010ho/submissions/15527888

  • 半開区間にすれば、そのまま宿の距離になる

f:id:tkr987:20200803071310p:plain

制約から移動距離をO(1)で求めたいので累積和にする。移動開始をs、移動終了をt、としたとき移動がマイナスだと区間が[t, s)となってしまうが、[min(s, t), max(s, t))とすればシンプルに実装できる。