Submission #1153469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153469		Dan4Life	Bitaro's travel (JOI23_travel)	C++20	100 / 100	436 ms	69928 KiB

travel

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
using ar3 = array<int,3>;

const int mxN = (int)2e5+10;
const int INF = (int)2e9;
const ll LINF = (ll)2e18;
const int mxLg = 20;

int n, q;
bool vis[mxN];
int x[mxN], y[mxN], z[mxN];
int jmp[mxLg][mxN], jmp2[mxLg][mxN];

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n; stack<int> S;
    for(int i = 0; i < n; i++) cin >> x[i];
    for(int i = 1; i < n; i++) y[i] = 2*x[i]-x[i-1];
    for(int i = 0; i < n-1; i++) z[i] = 2*x[i]-x[i+1];
    for(int i = 1; i < n; i++){
        while(sz(S) and y[S.top()] <= y[i]) S.pop();
        if(sz(S)) jmp[0][i]=S.top();
        S.push(i);
    }
    S = stack<int>();
    for(int j = 0; j < mxLg; j++)
        for(int i = 0; i < n; i++)
            jmp2[j][i] = n-1;
    for(int i = n-2; i >= 0; i--){
        while(sz(S) and z[S.top()]>=z[i]) S.pop();
        if(sz(S)) jmp2[0][i] = S.top();
        S.push(i);
    }
    for(int j = 1; j < mxLg; j++)
        for(int i = 0; i < n; i++)
            jmp[j][i] = jmp[j-1][jmp[j-1][i]],
            jmp2[j][i] = jmp2[j-1][jmp2[j-1][i]];
    cin >> q;
    while(q--){
        int s, l = 0, r = n-1;
        int ans = 0; cin >> s;
        int i = min<int>(n-1,lower_bound(x,x+n,s)-x);
        if(i and abs(x[i-1]-s) <= abs(x[i]-s)) i--;
        l = r = i, ans=abs(x[i]-s);
        while(1){
            if(!l or r==n-1){ 
                if(l or r!=n-1) ans+=x[n-1]-x[0];
                break;
            }

            int L = l, R = r;
            for(int j = mxLg-1; j>=0; j--)
                if(jmp[j][l] and y[jmp[j][l]]<=x[r+1])
                    l = jmp[j][l];
            if(l and y[l] <= x[r+1]) l=jmp[0][l];
            ans+=x[L]-x[l];

            if(!l or r==n-1){
                if(l or r!=n-1) ans+=x[n-1]-x[0];
                break;
            }

            ans+=x[r]-x[l];

            for(int j = mxLg-1; j>=0; j--)
                if(jmp2[j][r] and z[jmp2[j][r]]>x[l-1])
                    r = jmp2[j][r];
            if(r<n-1 and z[r]>x[l-1]) r=jmp2[0][r];
            ans+=x[r]-x[R];
        
            if(!l or r==n-1){
                if(l or r!=n-1) ans+=x[n-1]-x[0];
                break;
            }

            ans+=x[r]-x[l];
        }
        cout << ans << "\n";
    }
}

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