#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]=0;
}
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(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:90:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
90 | for(int i=1;i<=n;i++)cin>>x[i];x[0]=x[1],x[n+1]=x[n];
| ^~~
travel.cpp:90:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
90 | for(int i=1;i<=n;i++)cin>>x[i];x[0]=x[1],x[n+1]=x[n];
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3064 ms |
12892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3064 ms |
12892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3056 ms |
12892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3064 ms |
12892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
