Submission #1247338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247338		giaminhha	Bitaro's travel (JOI23_travel)	C++20	100 / 100	359 ms	4156 KiB

travel

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int ll

using namespace std;
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int, int> pii;
const int mod = 2147483647;
const int inf = 1e9 + 7;
const int N = 2e5 + 5;

ll x[N];
signed main(){
    fastio
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> x[i];
    int q; cin >> q;
    while(q--){
        ll s; cin >> s;
        int l, r; 
        int pos = lower_bound(x + 1, x + n + 1, s) - x;
        if(pos == n + 1){
            l = r = pos - 1;
        }
        else if(x[pos] == s || pos == 1 || (x[pos] - s) < (s - x[pos - 1])){
            l = r = pos;
        }
        else{
            l = r = pos - 1;
        }
        ll ans = abs(x[l] - s);
        s = x[l];
        while(true){
            if(l == 1){
                ans += abs(x[n] - s);
                break;
            }
            if(r == n){
                ans += abs(s - x[1]);
                break;
            }
            int le = x[l -1], ri = x[r + 1];
            if(abs(le - s) <= abs(ri - s)){
                int p = lower_bound(x + 1, x + n + 1, 2 * s - ri) - x;
                ans += abs(s - x[p]);
                s = x[p];
                l = p;
                continue;
            }
            else{
                int p = upper_bound(x + 1, x + n + 1, 2 * s - le) - x - 1;
                ans += abs(s - x[p]);
                s = x[p];
                r = p;
                continue;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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