Submission #1247319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247319		sourismkii	Bitaro's travel (JOI23_travel)	C++20	100 / 100	356 ms	4180 KiB

travel

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define is insert
#define pb push_back
#define pii pair<int, int>
#define pll pair<long long, long long>
#define X first
#define Y second
#define vi vector<int>
#define vpi vector<pair<int, int>>
#define msi multiset<int>
#define int long long
const int m97 = (int)1e9+7;
const int m83 = 998244353;
const int N = 200005;
const int K = 5;
const int inf = (int)1e18;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, s, l, r, q, ans;
int x[N];

void solve(){
	cin >> n;
	for(int i=1; i<=n; i++){
		cin >> x[i];
	}
	cin >> q;
	while(q--){
		cin >> s;
		int pos = lower_bound(x + 1, x + n + 1, s) - x;
		if(pos == n + 1) l = r = n;
		else if(pos == 1 || x[pos] == s || ((x[pos] - s) < (s - x[pos - 1]))) l = r = pos;
		else l = r = pos - 1;
		ans = abs(x[l] - s);
		s = x[l];	
		while(1){
			if(l == 1){
				ans += abs(x[n] - s);
				break;
			}
			else if(r == n){
				ans += abs(s - x[1]);
				break;
			}
			int nl = x[l - 1];
			int nr = x[r + 1];
			if(abs(s - nl) <= abs(s - nr)){
				int p = lower_bound(x + 1, x + n + 1, 2 * s - nr) - x;
				ans += abs(s - x[p]);
				l = p;
				s = x[p];
			}
			else{
				int p = upper_bound(x + 1, x + n + 1, 2 * s - nl) - x - 1;
				ans += abs(s - x[p]);
				r = p;
				s = x[p];
			}
		}
		cout << ans << "\n";
	}
}

signed main(){
//	freopen("*.INP", "r", stdin);
//    freopen("*.OUT", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tt = 1; //cin >> tt;
    while(tt--){
    	solve();
	}
}

/*
sample



*/

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