Submission #918920

#	Time	Username	Problem	Language	Result	Execution time	Memory
918920		esomer	Bitaro's travel (JOI23_travel)	C++17	0 / 100	1 ms	600 KiB

travel

#include <bits/stdc++.h>

using namespace std;

int msb[200001];

int getMax(int l, int r, vector<vector<int>>& dp){
    int k = msb[r - l + 1];
    return max(dp[k][r], dp[k][l + (1 << k) - 1]);
}

int getMin(int l, int r, vector<vector<int>>& dp){
    int k = msb[r - l + 1];
    return min(dp[k][r], dp[k][l + (1 << k) - 1]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<int> X(n);
    for(auto &i : X) cin >> i;
    vector<vector<int>> goLeft(20, vector<int> (n, 2e9+1));
    vector<vector<int>> goRight(20, vector<int> (n, -2e9-1));
    for(int k = 0; k < 20; k++){
        for(int i = 0; i < n; i++){
            if(k == 0){
                if(i == 0 || i == n - 1) continue;
                goLeft[k][i] = 2 * X[i] - X[i-1];
                goRight[k][i] = 2 * X[i] - X[i+1];
            }else{
                if(i - (1 << (k-1)) < 0){
                    goLeft[k][i] = goLeft[k-1][i];
                    goRight[k][i] = goRight[k-1][i];
                }else{
                    goLeft[k][i] = max(goLeft[k-1][i], goLeft[k-1][i-(1<<(k-1))]);
                    goRight[k][i] = min(goRight[k-1][i], goRight[k-1][i-(1<<(k-1))]);
                }
            }
        }
    }
    int currExp = 1;
    int exp = -1;
    for(int i = 1; i <= n; i++){
        if(i == currExp){
            exp++;
            currExp *= 2;
        }
        msb[i] = exp;
    }
    int q; cin >> q;
    while(q--){
        int x; cin >> x;
        int lo = 0;
        int hi = n - 1;
        int bst = -1;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(X[mid] >= x){
                bst = mid;
                hi = mid - 1;
            }else lo = mid + 1;
        }
        long long dist = 0;
        if(bst == -1){
            dist = X[0] - x;
            x = 0;
        }else if(bst == n-1){
            dist = x - X[n-1];
            x = n - 1;
        }else{
            if(x - X[bst] <= X[bst+1]-x){
                dist = x - X[bst];
                x = bst;
            }else{
                dist = X[bst+1] - x;
                x = bst + 1;
            }
        }
        int l = x, r = x;
        while(l != 0 && r != n - 1){
            if(X[x] - X[l - 1] <= X[r+1] - X[x]){
                lo = 0;
                hi = l - 1;
                bst = -1;
                while(lo <= hi){
                    int mid = (lo + hi) / 2;
                    if(getMax(mid, l - 1, goLeft) > X[r+1]){
                        bst = mid;
                        lo = mid + 1;
                    }else hi = mid - 1;
                }
                dist += X[x] - X[bst];
                l = bst;
                x = bst;
            }else{
                lo = r+1;
                hi = n - 1;
                bst = -1;
                while(lo <= hi){
                    int mid = (lo + hi) / 2;
                    if(X[l-1] >= getMin(r+1, mid, goRight)){
                        bst = mid;
                        hi = mid - 1;
                    }else lo = mid + 1;
                }
                dist += X[bst] - X[x];
                r = bst;
                x = bst;
            }
        }
        dist += X[n-1] - X[0];
        cout << dist << "\n";
    }
}

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