ABC119 D - Lazy Faith

問題
提出コード

解法

すごく簡単にいうと、それぞれのクエリに対して、解の候補が8通りしかありません。なので、調べればよいです。
今いる地点をとしたときに、より左側にある寺(神社も同様)のうち、一番近いものを1つみつけてひっぱってきます。右側も同様です。
この操作で、寺が2つ、神社が2つひっぱってくることができました。
あとは、それぞれの寺と神社の組み合わせを試していけばよいです。

• 寺と神社が同じ側に存在する場合
  どちらもより右側、もしくは左側に存在する場合です。
  これは、と寺(神社)の距離のうち、大きい方が最短距離になります。

• 寺と神社が逆側に存在する場合
  例えば、寺が左側、神社が右側にある場合です。
  これは、まずと神社(寺)の距離が近い方へ行き、そこから、逆側へいけばよいです。
  (との距離の小さい方+寺と神社の距離)
  になります。
  
  に最も近い寺と神社は、二分探索をうまく利用することで探すことができます。upper_boundを使ってを調べると、見つかった場所が、より右側で最も近い場所、そしてその1つ前の要素が、左側で最も近い場所になります。
  あとは、これを使って4箇所の位置を特定し、上の4通りを調べ、一番距離が短かったものを出力、ということをクエリの回数だけ繰り返せば答えとなります。
  
  

  感想

  実装悩んでいる暇があったら書いてしまえ！ということで実装していたら、とてつもないスパゲッティコードができあがりました。もうすこしスピーディかつ綺麗に書きたいものですね。
  最初、クエリの問題なので、どうせ前計算かなんかだろう、と思っていたのですが、の制約的に前計算が難しそうであることがわかります。そして、座標1からまで1周することすらかなわないので、二分探索がからんでいそう、となります。そして、よくよく考えれば、最も近いのはこの4通りしかなさそう、となるので、あとはこの4通りを調べるコードを書けばいい！となりました。
  考察自体は久々に瞬殺できた気がします。