ABC119D D - Lazy Faith (400)

D - Lazy Faith

概要

数直線上にA項の数列s（神社の位置）とB項の数列t（寺の位置）がある。Q項の数列xの各項xiについて、次の数値を答えよ。

• xiからスタートして、sの項とtの項に1つずつ移動するときの最小の移動距離(sとtはどちらから移動してもよい)

制約

1 ≦ A, B, Q ≦10^5
1 ≦ si, ti, xi ≦ 10^10

方針

愚直に移動させてゆく。移動先を見つけるには2分探索(lower_bound)を使用すると制約をクリアできる。
神社に先に行く/寺に先に行く、神社・寺それぞれについて右に行く/左に行くで合計8通りの移動を考える。
右に行くケースはlower_boundそのまま、左に行くケースはイテレータを1つ戻すとよい。
右端にいるケース・左端にいるケースでは左に行けない・右に行けない場合があるため取り除く。

解答

Submission #4377334 - AtCoder Beginner Contest 119

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int A, B, Q;
	cin >> A >> B >> Q;
 
	vector<ll> v(A);
	rep(i, A) cin >> v[i];
 
	vector<ll> w(B);
	rep(i, B) cin >> w[i];
 
	rep(i, Q){
		ll x;
		cin >> x;
 
		ll ans = 1LL << 62;
 
		// 右神社　→　右寺
		if(x <= v[A-1]){
			ll t = 0;
			auto it = lower_bound(v.begin(), v.end(), x);
			t += abs(*it - x);
			if(*it <= w[B-1]){
				auto it2 = lower_bound(w.begin(), w.end(), *it);
				t += abs(*it2 - *it);
				ans = min(ans, t);
			}
		}
 
		// 右神社　→　左寺
		if(x <= v[A-1]){
			ll t = 0;
			auto it = lower_bound(v.begin(), v.end(), x);
			t += abs(*it - x);
			if(*it >= w[0]){
				auto it2 = lower_bound(w.begin(), w.end(), *it);
				t += abs(*(it2-1) - *it);
				ans = min(ans, t);
			}
		}
 
		// 左神社　→　右寺
		if(x >= v[0]){
			ll t = 0;
			auto it = lower_bound(v.begin(), v.end(), x);
			it--;
			t += abs(*it - x);
			if(*it <= w[B-1]){
				auto it2 = lower_bound(w.begin(), w.end(), *it);
				t += abs(*it2 - *it);
				ans = min(ans, t);
			}
		}
 
		// 左神社　→　左寺
		if(x >= v[0]){
			ll t = 0;
			auto it = lower_bound(v.begin(), v.end(), x);
			it--;
			t += abs(*it - x);
			if(*it >= w[0]){
				auto it2 = lower_bound(w.begin(), w.end(), *it);
				it2--;
				t += abs(*it2 - *it);
				ans = min(ans, t);
			}
		}
 
		// 右寺　→　右神社
		if(x <= w[B-1]){
			ll t = 0;
			auto it = lower_bound(w.begin(), w.end(), x);
			t += abs(*it - x);
			if(*it <= v[A-1]){
				auto it2 = lower_bound(v.begin(), v.end(), *it);
				t += abs(*it2 - *it);
				ans = min(ans, t);
			}
		}
 
		// 右寺　→　左神社
		if(x <= w[B-1]){
			ll t = 0;
			auto it = lower_bound(w.begin(), w.end(), x);
			t += abs(*it - x);
			if(*it >= v[0]){
				auto it2 = lower_bound(v.begin(), v.end(), *it);
				t += abs(*(it2-1) - *it);
				ans = min(ans, t);
			}
		}
 
		// 左寺　→　右神社
		if(x >= w[0]){
			ll t = 0;
			auto it = lower_bound(w.begin(), w.end(), x);
			it--;
			t += abs(*it - x);
			if(*it <= v[A-1]){
				auto it2 = lower_bound(v.begin(), v.end(), *it);
				t += abs(*it2 - *it);
				ans = min(ans, t);
			}
		}
 
		// 左寺　→　左神社
		if(x >= w[0]){
			ll t = 0;
			auto it = lower_bound(w.begin(), w.end(), x);
			it--;
			t += abs(*it - x);
			if(*it >= v[0]){
				auto it2 = lower_bound(v.begin(), v.end(), *it);
				it2--;
				t += abs(*it2 - *it);
				ans = min(ans, t);
			}
		}
 
		cout << ans << endl;
	}
}