Submission #1181670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181670		Gray	Bitaro's travel (JOI23_travel)	C++20	15 / 100	3093 ms	34784 KiB

travel

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)1e9
#define MOD 998244353

struct Fenwick{
    vector<ll> tr_pref, tr_suff;
    ll n, offs;
    Fenwick(ll N, ll _offs=10){
        offs=_offs; n = N+2*offs;
        tr_pref.resize(n+1, -INF); tr_suff.resize(n+1, -INF);
    }
    void add_pref(ll i, ll x){
        i+=offs;
        for (; i<=n; i+=(-i&i)){
            tr_pref[i]=max(tr_pref[i], x);
        }
    }
    void add_suff(ll i, ll x){
        i+=offs;
        for (; i; i-=(-i&i)){
            tr_suff[i]=max(tr_suff[i], x);
        }
    }
    ll get_pref(ll i){
        i+=offs; ll res=-INF;
        for (; i; i-=(-i&i)){
            res=max(res, tr_pref[i]);
        }
        return res;
    }
    ll get_suff(ll i){
        i+=offs; ll res=-INF;
        for (; i<=n; i+=(-i&i)){
            res=max(res, tr_suff[i]);
        }
        return res;
    }
};

struct sparse{
    vector<vector<ll>> st;
    vector<ll> log;
    ll n;
    sparse(ll N, vector<ll> &a){
        n=N; log.resize(n+1);
        for (ll i=2; i<=n; i++) log[i]=log[i/2]+1;
        st.resize(log[n]+1, vector<ll>(n));
        st[0] = a;
        for (ll i=1; i<=log[n]; i++){
            for (ll j=0; j<=n-(1<<i); j++){
                st[i][j] = max(st[i-1][j], st[i-1][j+(1ull<<(i-1))]);
            }
        }
    }
    ll query(ll l, ll r){
        ll lg = log[r-l+1];
        return max(st[lg][l], st[lg][r-(1<<lg)+1]);
    }
};

void solve(){
    ll n, q; cin >> n;
    vector<ll> x(n);
    for (ll i=0; i<n; i++){
        cin >> x[i];
    }
    vector<ll> tola(n, -INF), tora(n, -INF);
    for (ll i=0; i<n; i++){
        if (i<n-1) tora[i] = (x[i+1]-2*x[i]);
        if (i) tola[i] = (2*x[i]-x[i-1]);
    }
    sparse tl(n, tola), tr(n, tora);
    cin >> q;
    while (q--){
        ll sp; cin >> sp;
        ll ind = lower_bound(x.begin(), x.end(), sp)-x.begin();
        ll l, r, cur; ll res=0;
        if (ind<(ll)x.size() and ind>0){
            if (x[ind]-sp<sp-x[ind-1]){
                l=r=ind; res+=x[ind]-sp;
            }else{
                l=r=ind-1; res+=sp-x[ind-1];
            }
        }else if (ind==(ll)x.size()){
            l=r=ind-1; res+=sp-x[ind-1];
        }else{
            l=r=ind; res+=x[ind]-sp;
        }
        cur=l;
        while (l>0 or r<n-1){
            if (l>0 and r<n-1){
                if (x[cur]-x[l-1]<=x[r+1]-x[cur]){
                    ll lo=0, hi=l;
                    while (lo+1<hi){
                        ll mid = (lo+hi)/2;
                        if (tl.query(mid, l-1)>x[r+1]) lo=mid;
                        else hi=mid;
                    }
                    res+=x[cur]-x[lo]; l=lo; cur=l;
                }else{
                    ll lo=r, hi=n-1;
                    while (lo+1<hi){
                        ll mid = (lo+hi)/2;
                        if (tl.query(r+1, mid)>=-x[l-1]) hi=mid;
                        else lo=mid;
                    }
                    res+=x[hi]-x[cur]; r=hi; cur=r;
                }
            }else if (l>0){
                res+=x[cur]-x[0]; l=0;
            }else{
                res+=x[n-1]-x[cur]; r=n-1;
            }
        }
        cout << res << ln;
    }
}

/*
-> : x[i+1]-2*x[i]>=-cord
<- : 2*x[i]-x[i-1]>cord
*/

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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