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

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

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

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