#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=0;
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-1)<=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+1,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';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2020 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
1884 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
