Submission #878333

#	Time	Username	Problem	Language	Result	Execution time	Memory
878333		LucaIlie	Bitaro's travel (JOI23_travel)	C++17	100 / 100	411 ms	11308 KiB

travel

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;
const long long INF = 1e9 + 5;
int leftP[MAX_N + 2], rightP[MAX_N + 2];
long long x[MAX_N + 2], ans[MAX_N + 2];
int n;

int solve( int i ) {
    if ( ans[i] > 0 )
        return ans[i];

    if ( i == 1 )
        ans[i] = x[n] - x[1];
    else if ( i == n )
        ans[i] = x[n] - x[1];
    else if ( i == leftP[i] )
        ans[i] = x[rightP[i]] - x[i] + solve( rightP[i] );
    else
        ans[i] = x[i] - x[leftP[i]] + solve( leftP[i] );
    return ans[i];
}

int main() {
    cin >> n;
    for ( int i = 1; i <= n; i++ )
        cin >> x[i];
    x[0] = -INF;
    x[n + 1] = 3 * INF;

    vector<int> stLeft;
    stLeft.push_back( 0 );
    for ( int i = 1; i <= n; i++ ) {
        int l = 0, r = stLeft.size();
        while ( r - l > 1 ) {
            int mid = (l + r) / 2;
            int p = stLeft[mid];
            if ( x[p + 1] - x[p] <= x[i + 1] - x[p + 1] )
                r = mid;
            else
                l = mid;
        }
        leftP[i] = stLeft[l] + 1;
        while ( !stLeft.empty() && 2 * x[i + 1] - x[i] >= 2 * x[stLeft.back() + 1] - x[stLeft.back()] )
            stLeft.pop_back();
        stLeft.push_back( i );
    }

    vector<int> stRight;
    stRight.push_back( n + 1 );
    for ( int i = n; i >= 1; i-- ) {
        int l = 0, r = stRight.size();
        while ( r - l > 1 ) {
            int mid = (l + r) / 2;
            int p = stRight[mid];
            if ( x[p] - x[p - 1] < x[p - 1] - x[i - 1] )
                r = mid;
            else
                l = mid;
        }
        rightP[i] = stRight[l] - 1;
        while ( !stRight.empty() && 2 * x[i - 1] - x[i] <= 2 * x[stRight.back() - 1] - x[stRight.back()] )
            stRight.pop_back();
        stRight.push_back( i );
    }

    for ( int i = 1; i <= n; i++ )
        ans[i] = solve( i );
    
    int q;
    cin >> q;
    while ( q-- ) {
        int y;
        cin >> y;
        int l = 0, r = n + 1;
        while ( r - l > 1 ) {
            int mid = (l + r) / 2;
            if ( y >= x[mid] )
                l = mid;
            else
                r = mid;
        }

        if ( y - x[l] <= x[l + 1] - y )
            cout << y - x[l] + ans[l] << "\n";
        else
            cout << x[l + 1] - y + ans[l + 1] << "\n";
    }

    return 0;
}

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