Submission #945598

#	Time	Username	Problem	Language	Result	Execution time	Memory
945598		phoenix0423	Bitaro's travel (JOI23_travel)	C++17	100 / 100	348 ms	79128 KiB

travel

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0);
#pragma GCC optimize("Ofast","unroll-loops")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 3e5 + 5;
const int INF = 1e9 + 7;
int mn[maxn][20], mx[maxn][20];

signed main(void){
    fastio;
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin>>a[i];
    vector<int> b(n), c(n);
    for(int i = 0; i < n; i++){
        if(i == n - 1) mx[i][0] = INF;
        else mx[i][0] = 2 * a[i + 1] - a[i];
        if(!i) mn[i][0] = -INF;
        else mn[i][0] = 2 * a[i - 1] - a[i];
    }
    for(int i = 1; (1 << i) < n; 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;
    auto get_max = [&](int l, int r) -> int{
        int len = __lg(r - l + 1);
        return max(mx[l][len], mx[r - (1 << len) + 1][len]);
    };
    auto get_min = [&](int l, int r) -> int{
        int len = __lg(r - l + 1);
        return min(mn[l][len], mn[r - (1 << len) + 1][len]);
    };
    auto find_first_grt = [&](int l, int r, int tar) -> int{
        if(mx[r][0] > tar) return r;
        l--;
        while(l + 1 < r){
            int m = (l + r) / 2;
            if(get_max(m, r) > tar) l = m;
            else r = m;
        }
        return l;
    };
    auto find_first_sm = [&](int l, int r, int tar) -> int{
        if(mn[l][0] <= tar) return l;
        r++;
        while(l + 1 < r){
            int m = (l + r) / 2;
            if(get_min(l, m) <= tar) r = m;
            else l = m;
        }
        return r;
    };
    while(q--){
        int x;
        cin>>x;
        int stp = lower_bound(a.begin(), a.end(), x) - a.begin();
        if(stp == n) stp--;
        if(stp != 0 && x - a[stp - 1] <= a[stp] - x) stp--;
        int l = stp, r = stp, ans = abs(x - a[stp]);
        int d = 0;
        while(true){
            if(l == 0 || r == n - 1){
                ans += a[n - 1] - a[0];
                break;
            }
            ans += a[r] - a[l];
            if(d == 0){
                int tmp = find_first_grt(0, l - 1, a[r + 1]);
                ans += a[l] - a[tmp + 1];
                l = tmp + 1;
            }
            else{
                int tmp = find_first_sm(r + 1, n - 1, a[l - 1]);
                ans += a[tmp - 1] - a[r];
                r = tmp - 1;
            }
            d ^= 1;
        }
        cout<<ans<<"\n";
    }
}

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