perogram

D - Lazy Faith

Quiz

https://atcoder.jp/contests/abc119/tasks/abc119_d

Submit

https://atcoder.jp/contests/abc119/submissions/4374869

Note

  • xの位置から見て、一番近い右にある寺・神社
  • xの位置から見て、一番近い左にある寺・神社
  • をそれぞれ求める
  • 右の神社に行って左の寺に行くなどの各パターンで距離を求めて、その中の最小値が答え
  • 一番近い神社・寺は二分探索 (lower_bound, upper_bound)で求まる

注意点

  • 左に寺がない時などを意識する必要がある
  • イテレータとV.begin(), V.end()を比較すれば検知できる
  • 寺配列、神社配列にそれぞれ-inf, infを挿入すれば確実に左右に寺・神社がある状態にできる
    • 番兵
  • そのテクニックは次回使いたい