Submission #1007995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007995		tosivanmak	Bitaro's travel (JOI23_travel)	C++17	0 / 100	3092 ms	181076 KiB

travel

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll lg[200005];
struct Sparse{
  vector<vector<ll> >stmin,stmax;
    vector<ll>arr;
    void init(ll n){
        stmin.resize(n+5),stmax.resize(n+5),arr.resize(n+5);
        for(int i=0;i<n+5;i++){
            stmax[i].resize(21);
            stmin[i].resize(21);
        }
    }
    void build(ll n){
        for(int i=1;i<=n;i++){
            stmax[i][0]=stmin[i][0]=arr[i];
        }
        for(int j=1;j<=20;j++){
            for(int i=1;i<=n;i++){
                if(i+(1<<(j-1))<=n){
                    stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
                    stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
                }
            }
        }
    }
    ll maximum(ll ql, ll qr){
        ll rng=lg[qr-ql+1];
        return max(stmax[ql][rng],stmax[qr-(1<<rng)+1][rng]);
    }
    ll minimum(ll ql, ll qr){
        ll rng=lg[qr-ql+1];
        return min(stmin[ql][rng],stmin[qr-(1<<rng)+1][rng]);
    }
}to_left,to_right;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    for(int i=2;i<=200000;i*=2){
        lg[i]=1;
    }
    for(int i=3;i<=200000;i++){
        lg[i]+=lg[i-1];
    }
    ll n;
    cin>>n;
    to_left.init(n),to_right.init(n);
    ll x[n+5];map<ll,ll>mp;
    x[0]=x[n+1]=1e18;
    vector<ll>rev,xx;
    rev.push_back(1e18);
    for(int i=1;i<=n;i++){
        cin>>x[i];mp[x[i]]=i;
        rev.push_back(-x[i]);
        xx.push_back(x[i]);
    }
    for(int i=1;i<=n-1;i++){
        to_left.arr[i]=2*x[i+1]-x[i];
    }
    for(int i=2;i<=n;i++){
        to_right.arr[i]=2*x[i-1]-x[i];
    }
    to_left.build(n),to_right.build(n);
    // x[k]>=min(2*x[i+1]-x[i])
    // x[k]<2*x[i-1]-x[i]
    reverse(rev.begin(),rev.end());
    xx.push_back(1e18);
    ll q;
    cin>>q;
    while(q--){
        ll k;
        cin>>k;
        ll bpos=lower_bound(xx.begin(),xx.end(),k)-xx.begin()+1;
        ll fpos=n+1-(lower_bound(rev.begin(),rev.end(),-k)-rev.begin()+1);
        ll starting=0;
        if(abs(x[fpos]-k)<=abs(x[bpos]-k)){
            starting=fpos;
        }
        else{
            starting=bpos;
        }
            ll l=starting,r=starting,pos=x[starting],ans=abs(k-x[starting]);
            while(l!=1&&r!=n){
                ll lb=1,rb=l-1;
                if(pos-x[l-1]<=x[r+1]-pos){
                    while(lb<rb){
                        ll mid=(lb+rb)>>1;
                        if(to_left.maximum(mid,l-2)<=x[r+1]){
                            rb=mid;
                        }
                        else lb=mid+1;
                    }
                    ans+=(pos-x[lb]);pos=x[lb];l=lb;
                    // cout<<lb<<' '; 
                }
                if(l==1||r==n)break;
                if(x[r+1]-pos<pos-x[l-1]){
                    lb=r+1,rb=n;
                    while(lb<rb){
                        ll mid=(lb+rb+1)>>1;
                        if(to_right.minimum(r+2,mid)<x[l-1]){
                            lb=mid;
                        }
                        else rb=mid-1;
                    }
                    ans+=(x[rb]-pos);pos=x[rb];r=rb;
                    // cout<<lb<<" ";
                }
                if(l==1||r==n)break;
            }
            if(l==1){
                ans+=x[n]-pos;
            }
            else{
                ans+=pos-x[1];
            }
            cout<<ans<<'\n';
    }
}

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