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を挿入すれば確実に左右に寺・神社がある状態にできる
- 番兵
- そのテクニックは次回使いたい
