AtCoder Beginner Contest 119：D - Lazy Faith

問題

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

考え方

各クエリに対して O(logN) ないしは O(1) で答えないといけない。神社用と寺用のTreeSet(二分探索木)に各 s_i, t_i をあらかじめ入れておけばクエリごとにある位置 x_j に対して左右にある最短の神社と寺の位置を求めることができる。

あとは神社と寺を訪問するパターンを網羅すれば最短距離を求めることができる。右の神社→左の寺...など全 8 パターンある。

Submission #4380845 - AtCoder Beginner Contest 119

実装テクとしては右端と左端に番兵 (-2^{60}, 2^{60}) 程度の値を入れてしまうのが楽。

どこに着目して考察するべきだったか

何がバグっていたか

得た知見(典型ポイント)

類題