Submission #969095

#	Time	Username	Problem	Language	Result	Execution time	Memory
969095		dong_gas	Bitaro's travel (JOI23_travel)	C++17	100 / 100	427 ms	8120 KiB

travel

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/extc++.h>
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ll n, q;

void solve() {
    cin>>n;
	vector<ll> x(n);
	for(ll& xx: x) cin>>xx;
	cin>>q;
	while(q --> 0) {
		ll s; cin>>s;
		ll idx=lower_bound(all(x),s)-x.begin(), ans=0;
		ll l, r;
		if(idx==0) {
			cout<<x[n-1]-s<<'\n';
			continue;
		}
		else if(idx==n) {
			cout<<s-x[0]<<'\n';
			continue;
		}
		else {
			ll rd=x[idx]-s, ld=s-x[idx-1];
			if(ld<=rd) ans+=ld, l=r=idx-1, s=x[idx-1];
			else ans+=rd, l=r=idx, s=x[idx];
		}
		//l~r까지 완료 함...
		while(1) {
			if(l==0) {
				ans+=x[n-1]-s;
				break;
			}
			if(r==n-1) {
				ans+=s-x[0];
				break;
			}
			bool chk=false;
			if(l==1 && r==3) chk=true;
			if(s-x[l-1]<=x[r+1]-s) {//좌
				ll i=lower_bound(all(x),2*s-x[r+1])-x.begin();
				ans+=s-x[i];
				s=x[i];
				l=i;
			}
			else {				
				ll i=lower_bound(all(x),2*s-x[l-1])-x.begin()-1;
				//if(i==n) i--;
				//if(chk) cout<<i<<endl;
				ans+=x[i]-s;
				s=x[i];
				r=i;
			}
			if(chk) {
				//cout<<ans<<' '<<l<<' '<<r<<' '<<s<<endl;
				//return;
			}
			
		}
		cout<<ans<<'\n';
	}
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc=1; //cin>>tc;
    while(tc--) solve();
} 

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55