Submission #1247332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247332		giaminhha	Bitaro's travel (JOI23_travel)	C++20	0 / 100	0 ms	328 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);

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];
    sort(x + 1, x + n + 1);
    int q; cin >> q;
    while(q--){
        ll s; cin >> s;
        int l, r; 
        int pos = lower_bound(x + 1, x + n + 1, s) - x;
        int ri = pos, le = pos - 1;
        if(x[ri] == s) ++ri;
        if(x[le] == s) --le;
        if(abs(x[ri] - s) < abs(x[le] - s)){
            l = r = ri;
        }
        else l = r = le;
        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;
            }
            le = l - 1, ri = r + 1;
            if(abs(x[le] - s) <= abs(x[ri] - s)){
                int p = lower_bound(x + 1, x + n + 1, 2 * s - x[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 - x[le]) - x - 1;
                ans += abs(s - x[p]);
                s = x[p];
                r = p;
                continue;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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