#include <bits/stdc++.h>
using namespace std;
const int nx=2e5+5;
int n, v[nx], q, s, l, r, dr[nx], dl[nx];
long long ans;
bool isl;
struct rsegtree
{
int d[4*nx];
void build(int l, int r, int i)
{
if (l==r) return void(d[i]=dr[l]);
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=min(d[2*i], d[2*i+1]);
}
int query(int l, int r, int i, int ql, int qr, int vl)
{
if (qr<l||r<ql) return -1;
if (ql<=l&&r<=qr&&!(vl>d[i])) return -1;
if (l==r) return l;
int md=(l+r)/2, tmp=query(l, md, 2*i, ql, qr, vl);
if (tmp!=-1) return tmp;
return query(md+1, r, 2*i+1, ql, qr, vl);
}
} rs;
struct lsegtree
{
int d[4*nx];
void build(int l, int r, int i)
{
if (l==r) return void(d[i]=dl[l]);
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=max(d[2*i], d[2*i+1]);
}
int query(int l, int r, int i, int ql, int qr, int vl)
{
if (qr<l||r<ql) return -1;
if (ql<=l&&r<=qr&&vl>=d[i]) return -1;
if (l==r) return l;
int md=(l+r)/2, tmp=query(md+1, r, 2*i+1, ql, qr, vl);
if (tmp!=-1) return tmp;
return query(l, md, 2*i, ql, qr, vl);
}
} ls;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n;
for (int i=1; i<=n; i++) cin>>v[i];
for (int i=1; i<n; i++) dr[i]=2*v[i]-v[i+1];
dr[n]=-2e9;
for (int i=2; i<=n; i++) dl[i]=2*v[i]-v[i-1];
dl[1]=2e9;
//for (int i=1; i<=n; i++) cout<<dl[i]<<'\n';
v[0]=-2e9; v[n+1]=2e9;
rs.build(1, n, 1);
ls.build(1, n, 1);
//cout<<ls.query(1, n, 1, 1, 2, 3)<<'\n';
cin>>q;
while (q--)
{
cin>>s;
int cl=lower_bound(v, v+n+2, s)-v;
if (s-v[cl]<=v[cl+1]-s) l=r=cl, ans=s-v[cl];
else l=r=cl+1, ans=v[cl+1]-s;
isl=1;
int cnt=0;
while (l!=1&&r!=n&&++cnt!=5)
{
//cout<<l<<' '<<r<<' '<<ans<<'\n';
if (isl&&l!=1)
{
int np=ls.query(1, n, 1, 1, l, v[r+1]);
ans+=v[r]-v[np];
l=np;
}
if (!isl&&r!=n)
{
int np=rs.query(1, n, 1, r, n, v[l-1]);
ans+=v[np]-v[l];
r=np;
}
isl=!isl;
}
//cout<<l<<' '<<r<<' '<<ans<<'\n';
if (r==n) ans+=v[r]-v[1];
else ans+=v[n]-v[l];
cout<<ans<<'\n';
}
}
/*
10
1 2 3 4 5 6 7 8 9 10
1
2
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |