Submission #934472

#	Time	Username	Problem	Language	Result	Execution time	Memory
934472		Pacybwoah	Bitaro's travel (JOI23_travel)	C++17	100 / 100	231 ms	42588 KiB

travel

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
// lst: max
// rst: min
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int> vec(n+1,-1e9);
    for(int i=1;i<=n;i++) cin>>vec[i];
    vector<vector<int> > m(2,vector<int>(n+1)),lst(20,vector<int>(n+1)),rst(20,vector<int>(n+1)); // [0]=left [1]=right
    for(int i=1;i<n;i++) m[0][i]=2*vec[i+1]-vec[i],lst[0][i]=m[0][i];
    for(int i=2;i<=n;i++) m[1][i]=2*vec[i-1]-vec[i],rst[0][i]=m[1][i];
    for(int j=1;j<20;j++){
        for(int i=1;i+(1<<(j-1))<n;i++) lst[j][i]=max(lst[j-1][i],lst[j-1][i+(1<<(j-1))]);
        for(int i=2;i+(1<<(j-1))<=n;i++) rst[j][i]=min(rst[j-1][i],rst[j-1][i+(1<<(j-1))]);
    }
    vector<int> bases(n+1);
    for(int j=0;j<20;j++){
        for(int i=(1<<j);i<=min(1<<(j+1),n);i++) bases[i]=j;
    }
    auto query=[&](int l,int r,bool flag){
        int len=bases[r-l+1];
        if(flag) return min(rst[len][l],rst[len][r-(1<<len)+1]);
        else return max(lst[len][l],lst[len][r-(1<<len)+1]);
    };
    vector<ll> ans(n+1);
    //cout<<query(3,4,1)<<" "<<query(3,5,1)<<"\n";
    for(int i=1;i<=n;i++){
        if(i==1||i==n){
            ans[i]=vec[n]-vec[1];
            continue;
        }
        bool dire;
        int curl=i-1,curr=i+1;
        if(vec[i]-vec[curl]<=vec[curr]-vec[i]) dire=0,ans[i]+=vec[i]-vec[curl];
        else dire=1,ans[i]+=vec[curr]-vec[i];
        //cout<<dire;
        while(1){
            //cout<<i<<" "<<curl<<" "<<curr<<"\n";
            if(!dire){
                int l=0,r=curl;
                while(l<r){
                    int mid=((l+r)>>1)+1;
                    if(query(mid,curl,0)>vec[curr]){
                        l=mid;
                    }
                    else r=mid-1;
                }
                if(l==0){
                    ans[i]+=1ll*(vec[curl]-vec[1]+vec[n]-vec[1]);
                    break;
                }
                else{
                    ans[i]+=1ll*(vec[curl]-vec[l+1]+vec[curr]-vec[l+1]);
                    curl=l;
                    dire=1;
                }
            }
            else{
                int l=curr,r=n+1;
                while(l<r){
                    int mid=((l+r)>>1);
                    if(query(curr,mid,1)<=vec[curl]){
                        r=mid;
                    }
                    else l=mid+1;
                }
                //cout<<l;
                if(l==n+1){
                    ans[i]+=1ll*(vec[n]-vec[curr]+vec[n]-vec[1]);
                    break;
                }
                else{
                    ans[i]+=1ll*(vec[r-1]-vec[curr]+vec[r-1]-vec[curl]);
                    curr=r;
                    dire=0;
                }
            }
        }
    }
    int q;
    cin>>q;
    ll num;
    for(int i=0;i<q;i++){
        cin>>num;
        if(num<vec[1]) cout<<vec[n]-num<<"\n";
        else if(num>vec[n]) cout<<num-vec[1]<<"\n";
        else{
            int pos=lower_bound(vec.begin(),vec.end(),num)-vec.begin();
            if(vec[pos]==num) cout<<ans[pos]<<"\n";
            else{
                if(num-vec[pos-1]<=vec[pos]-num) cout<<ans[pos-1]+num-vec[pos-1]<<"\n";
                else cout<<vec[pos]-num+ans[pos]<<"\n";
            }
        }
    }
}

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