Lazy Faith [AtCoder Beginner Contest 119 D]

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

解説

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

まず、lower_boundを知らない場合は学ぼう。
これを使うと、あるx以上で最も近い、Sの要素、Tの要素がO(logN)で得られる。
要素の添字を-1すると、x未満で最も近い要素も得られる。
　
さて、これであるxについて、寺と神社の左右で一番近い所が探せたことになる。
最適な動きは「左にずっと移動」「右にずっと移動」「左に行ってから右に移動」「右に行ってから左に移動」の4種。
これを実装する。
下の実装では、左→右と右→左はまとめて見ている。
寺と神社について左右で近い方を求めて、足し算する。
どちらも左だった場合、どちらも右だった場合で足し算してしまう可能性もあるが、この場合はずっと移動の方が
良い結果になるので、問題ない。
寺か神社のどちらかは往復になるので、*2をつけた2通りで小さい方を採用する。
　
あとは、xより小さい要素、大きい要素がない場合があるので、その辺を場合分けで注意して実装する。
注意が嫌なら、番兵として、先頭に-inf, 後尾にinfをつけて置けば無視できる。

int A, B, Q; ll S[101010], T[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> Q;
    rep(i, 0, A) cin >> S[i];
    rep(i, 0, B) cin >> T[i];

    rep(q, 0, Q) {
        ll x; cin >> x;
        ll ans = infl;
 
        // 左だけ
        if (S[0] < x and T[0] < x) {
            int s = lower_bound(S, S + A, x) - S - 1;
            int t = lower_bound(T, T + B, x) - T - 1;
            chmin(ans, max(x - S[s], x - T[t]));
        }
 
        // 右だけ
        if (x < S[A-1] and x < T[B-1]) {
            int s = lower_bound(S, S + A, x) - S;
            int t = lower_bound(T, T + B, x) - T;
            chmin(ans, max(S[s] - x, T[t] - x));
        }
 
        // 左右
        ll shrine = infl;
        if (S[0] < x) {
            int id = lower_bound(S, S + A, x) - S - 1;
            chmin(shrine, x - S[id]);
        }
        if (x < S[A - 1]) {
            int id = lower_bound(S, S + A, x) - S;
            chmin(shrine, S[id] - x);
        }
        
        ll temple = infl;
        if (T[0] < x) {
            int id = lower_bound(T, T + B, x) - T - 1;
            chmin(temple, x - T[id]);
        }
        if (x < T[B - 1]) {
            int id = lower_bound(T, T + B, x) - T;
            chmin(temple, T[id] - x);
        }
        chmin(ans, shrine*2 + temple);
        chmin(ans, shrine + temple * 2);
 
        printf("%lld\n", ans);
    }
}