Submission #780655

#	Time	Username	Problem	Language	Result	Execution time	Memory
780655		Cookie	Bitaro's travel (JOI23_travel)	C++14	100 / 100	523 ms	64320 KiB

travel

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("VNOICUP.INP");
ofstream fout("VNOICUP.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
//const int x[4] = {1, -1, 0, 0};
//const int y[4] = {0, 0, 1, -1};
const ll mod = 998244353;
const int mxn = 2e5 + 5, mxq = 2e5 + 5, sq = 400, mxv = 2e7 + 5;
//const int base = (1 << 18);
const ll inf = 2e9 + 5, neg = -69420;
int n;
ll x[mxn + 1], mx[mxn + 1][18], mn[mxn + 1][18];
ll getmn(int l, int r){
    int lg = __lg(r - l + 1);
    return(min(mn[l][lg], mn[r - (1 << lg) + 1][lg]));
}
ll getmx(int l, int r){
    int lg = __lg(r - l + 1);
    return(max(mx[l][lg], mx[r - (1 << lg) + 1][lg]));
}
void solve(ll s){
    int id = lower_bound(x, x + n + 1, s) - x;
    ll res, l, r;
    if(abs(x[id - 1] - s) <= abs(x[id] - s)){
        res = abs(x[id - 1] - s); l = r = id - 1;
    }else{
        l = r = id; res = x[id] - s;
    }
    bool turn = 1;
    while(l > 1 || r < n){
        if(turn){
            // go left
            int le = 1, ri = l - 1, ans = l;
            while(le <= ri){
                int mid = (le + ri) >> 1;
                if(getmx(mid, l - 1) <= x[r + 1]){
                    ans = mid; ri = mid - 1;
                }else{
                    le = mid + 1;
                }
            }
            res += x[l] - x[ans]; 
            if(r < n)res += x[++r] - x[ans];
            l = ans;
        }else{
            // go right
            int le = r + 1, ri = n, ans = r;
            while(le <= ri){
                int mid = (le + ri) >> 1;
                if(getmn(r, mid - 1) > x[l - 1]){
                    ans = mid; le = mid + 1;
                }else{
                    ri = mid - 1;
                }
            }
            res += x[ans] - x[r];
            if(l > 1)res += x[ans] - x[--l];
            r = ans;
        }
        turn = !turn;
    }
    cout << res << "\n";
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x[i]; 
    }
    x[0] = -inf; x[n + 1] = inf;
    for(int i = 0; i < n; i++){
        mx[i][0] = 2 * x[i + 1] - x[i]; mn[i][0] = -x[i + 1] + 2 * x[i];
    }
    for(int i = 1; i < 18; i++){
        for(int j = 0; j + (1 << i) - 1 < n; j++){
            mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]);
            mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]);
        }
    }
    int q; cin >> q;
    while(q--){
        int s; cin >> s;
        solve(s);
    }
    return(0);
}

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