oj.uz

Submission #993609

# Submission time Handle Problem Language Result Execution time Memory
993609 2024-06-06T08:14:22 Z imarn Bitaro's travel (JOI23_travel) C++14
0 / 100
 3 ms 13048 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int mxn=2e5+5;
int n;
ll x[mxn]{0};
struct mntree{
    ll t[4*mxn]{0};
    void build(){
        for(int i=0;i<4*mxn;i++)t[i]=2e18;
    }
    void update(int i,int l,int r,int idx,ll v){
        if(r<idx||l>idx)return;
        if(l==r)return void(t[i]=v);
        int m=(l+r)>>1;update(2*i,l,m,idx,v);update(2*i+1,m+1,r,idx,v);
        t[i]=min(t[2*i],t[2*i+1]);
    }
    pair<pii,int>query1(int i,int l,int r,int idx,ll v){
        if(r<idx)return {{1e9,1e9},1e9};
        if(l>=idx&&t[i]<=v)return {{l,r},i};
        else if(l>=idx&&t[i]>v)return {{1e9,1e9},1e9};
        int m=(l+r)>>1;
        return min(query1(2*i,l,m,idx,v),query1(2*i+1,m+1,r,idx,v));
    }
    int query(int i,int l,int r,ll v){
        if(l==r)return l;int m=(l+r)>>1;
        if(t[2*i]<=v)return query(2*i,l,m,v);
        else return query(2*i+1,m+1,r,v);
    }
    int cal(int i,ll v){
        pair<pii,int>res=query1(1,1,n,i,v);
        if(res.s==1e9)return n;
        return query(res.s,res.f.f,res.f.s,v);
    }
}sg1;
struct mxtree{
    ll t[4*mxn]{0};
    void build(){
        for(int i=0;i<4*mxn;i++)t[i]=-2e18;
    }
    void update(int i,int l,int r,int idx,ll v){
        if(r<idx||l>idx)return;
        if(l==r)return void(t[i]=v);
        int m=(l+r)>>1;update(2*i,l,m,idx,v);update(2*i+1,m+1,r,idx,v);
        t[i]=max(t[2*i],t[2*i+1]);
    }
    pair<pii,int>query1(int i,int l,int r,int idx,ll v){
        if(l>idx)return {{-1,-1},-1};
        if(r<=idx&&t[i]>v)return {{l,r},i};
        else if(r<=idx&&t[i]<=v)return {{-1,-1},-1};
        int m=(l+r)>>1;
        return max(query1(2*i,l,m,idx,v),query1(2*i+1,m+1,r,idx,v));
    }
    int query(int i,int l,int r,ll v){
        if(l==r)return l;int m=(l+r)>>1;
        if(t[2*i+1]>v)return query(2*i+1,m+1,r,v);
        else return query(2*i,l,m,v);
    }
    int cal(int i,ll v){
        pair<pii,int>res=query1(1,1,n,i,v);
        if(res.s==-1)return 1;
        return query(res.s,res.f.f,res.f.s,v);
    }
}sg2;
ll solve(int u){
    ll tt=0;
    int l=u,r=u;
    bool lef=1;
    while(l!=1||r!=n){
        if(l==1)return tt+x[n]-x[1];
        if(r==n)return tt+x[n]-x[1];
        if(lef){
            if(l==1)continue;
            int tl = sg2.cal(l,x[r+1]);
            tt +=x[r]-x[tl];l=tl;
        }
        else {
            if(r==n)continue;
            int tr = sg1.cal(r,x[l-1]);
            tt+=x[tr]-x[l];r=tr;
        }lef=!lef;
    }return tt;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;sg1.build();sg2.build();
    for(int i=1;i<=n;i++)cin>>x[i];x[0]=x[1],x[n+1]=x[n];
    for(int i=1;i<=n;i++){
        sg1.update(1,1,n,i,2*x[i]-x[i+1]);
        sg2.update(1,1,n,i,2*x[i]-x[i-1]);
    }int q;cin>>q;
    while(q--){
        ll y;cin>>y;
        int id = lower_bound(x+1,x+n+1,y)-x;
        if(id>=n)cout<<solve(n)+y-x[n]<<'\n';
        else if(id==1)cout<<solve(1)+x[1]-y<<'\n';
        else{
            if(x[id]-y<y-x[id-1])cout<<x[id]-y+solve(id)<<'\n';
            else cout<<y-x[id-1]+solve(id-1)<<'\n';
        }
    }
}

//left find max l such that       a[l]-a[l-1]>=a[r+1]-a[l]
//right find min r such that      a[r+1]-a[r]>=a[r]-a[l-1]

Compilation message

travel.cpp: In member function 'int mntree::query(int, int, int, long long int)':
travel.cpp:31:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   31 |         if(l==r)return l;int m=(l+r)>>1;
      |         ^~
travel.cpp:31:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   31 |         if(l==r)return l;int m=(l+r)>>1;
      |                          ^~~
travel.cpp: In member function 'int mxtree::query(int, int, int, long long int)':
travel.cpp:60:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   60 |         if(l==r)return l;int m=(l+r)>>1;
      |         ^~
travel.cpp:60:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   60 |         if(l==r)return l;int m=(l+r)>>1;
      |                          ^~~
travel.cpp: In function 'int main()':
travel.cpp:92:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   92 |     for(int i=1;i<=n;i++)cin>>x[i];x[0]=x[1],x[n+1]=x[n];
      |     ^~~
travel.cpp:92:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   92 |     for(int i=1;i<=n;i++)cin>>x[i];x[0]=x[1],x[n+1]=x[n];
      |                                    ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12988 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 13048 KB Output is correct
6 Correct 3 ms 12980 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Incorrect 2 ms 12892 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12988 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 13048 KB Output is correct
6 Correct 3 ms 12980 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Incorrect 2 ms 12892 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Incorrect 3 ms 12892 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12988 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 13048 KB Output is correct
6 Correct 3 ms 12980 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Incorrect 2 ms 12892 KB Output isn't correct
9 Halted 0 ms 0 KB -