AtCoder Beginner Contest 119:D - Lazy Faith
問題
解法
各クエリごとに x_i より左にある最寄りの神社・寺,x_i より右にある最寄りの神社・寺の場所を計算する.これは std::lower_bound() や std::upper_bound() を用いて O(logA), O(logB) で計算できる.あとは,神社と寺それぞれについて左か右のどちらの最寄りのものにいくかを4通り考え,それぞれでかかるコストを計算する.O(Q * (logA + logB)).
解答