제출 #1153421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153421		Dan4Life	Bitaro's travel (JOI23_travel)	C++20	0 / 100	3097 ms	580 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)1e9;
const ll LINF = (ll)2e18;
const int mxLg = 20;

int n, q;
int x[mxN], y[mxN];
int jmp[mxLg][mxN];

void solve(){
    cin >> n; stack<int> S;
    for(int i = 1; i <= n; i++) cin >> x[i];
    for(int i = 2; i <= n; i++) 
        y[i] = 2*x[i]-x[i-1];
    for(int i = 0; i < mxLg; i++) 
        for(int j = 1; j <= n; j++) 
            jmp[i][j]=1;
    for(int i = 2; 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);
    }
    for(int j = 1; j < mxLg; j++)
        for(int i = 1; i <= n; i++)
            jmp[j][i] = jmp[j-1][jmp[j-1][i]];
    cin >> q;
    while(q--){
        int s, ans=0, l=1, r=n; cin >> s;
        int pos = upper_bound(x+1,x+n+1,s)-x-1;
        if(pos>=n) l=r=n,ans+=abs(x[n]-s);
        else{
            if(abs(x[pos]-s) > abs(x[pos+1]-s)) pos++;
            ans+=abs(x[pos]-s),l=r=pos;
        }
        while(l!=1 and r!=n){
            int L = l, R = r;
            if(y[l] <= x[r+1]){
                for(int j = mxLg-1; j>=0;  j--)
                    if(jmp[j][l]!=1 and y[jmp[j][l]]<=x[r+1]) l=jmp[j][l];
                l=jmp[0][l];
                ans+=x[R]-x[l];
            }
            else{
                r = upper_bound(x+1,x+n+1,y[l])-x-1;
                ans+=x[r]-x[l];
            }
        }
        if(r==n){
            if(l!=1) ans+=x[n]-x[1];
        }
        if(l==1){
            if(r!=n) ans+=x[n]-x[1];
        }
        cout << ans << "\n";
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
}

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