#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=2e5+5;
int N,Q;
ll X[MX];
ll val[MX];
struct segtree {
ll t[4 * MX];
void update(int v, int l, int r, int pos, int val) {
if(l > pos || r < pos) return;
if(l == r) {
t[v] = val;
return;
}
int mid = (l + r) >> 1;
update(v * 2 + 0, l, mid + 0, pos, val);
update(v * 2 + 1, mid + 1, r, pos, val);
t[v] = min(t[v * 2 + 0], t[v * 2 + 1]);
}
ll query(int v, int l, int r, int ql, int qr) {
if(ql > r || qr < l) return 2e18;
if(ql <= l && qr >= r) return t[v];
int mid = (l + r) >> 1;
return min(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
}
} st;
struct ST {
ll t[4 * MX];
void update(int v, int l, int r, int pos, int val) {
if(l > pos || r < pos) return;
if(l == r) {
t[v] = val;
return;
}
int mid = (l + r) >> 1;
update(v * 2 + 0, l, mid + 0, pos, val);
update(v * 2 + 1, mid + 1, r, pos, val);
t[v] = max(t[v * 2 + 0], t[v * 2 + 1]);
}
int query(int v, int l, int r, int ql, int qr) {
if(ql > r || qr < l) return 0;
if(ql <= l && qr >= r) return t[v];
int mid = (l + r) >> 1;
return max(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
}
} tt;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N;
for(int i=1;i<=N;i++) cin>>X[i];
X[0]=-1e9;
X[N+1]=1e9;
for(int i=1;i<N;i++) st.update(1,1,N,i,2*X[i]-X[i+1]); // go right
st.update(1,1,N,N,-2e9);
for(int i=2;i<=N;i++) tt.update(1,1,N,i,2*X[i]-X[i-1]); // go left
tt.update(1,1,N,1,2e9);
for(int i=1;i<=N;i++) {
int p=i;
int j=i;
if(X[i]-X[i-1]<=X[i+1]-X[i]) {
val[p]+=X[i]-X[i-1];
j-=1;
} else {
val[p]+=X[i+1]-X[i];
j+=1;
}
while(!(min(i,j)==1 && max(i,j)==N)) {
int pi=i,pj=j;
if(i<j) {
int l=j,r=N,res=-1;
while(l<=r) {
int mid=(l+r)/2;
if(st.query(1,1,N,j,mid)>X[i-1]) {
res=mid,l=mid+1;
} else {
r=mid-1;
}
}
if(res==-1) {
val[p]+=X[j]-X[i];
swap(i,j);
continue;
}
res+=1;
val[p]+=X[res]-X[j];
val[p]+=X[res]-X[i];
j=res;
swap(i,j);
} else { // j < i
int l=1,r=j,res=-1;
while(l<=r) {
int mid=(l+r)/2;
if(tt.query(1,1,N,mid,j)<=X[i+1]) {
res=mid,r=mid-1;
} else {
l=mid+1;
}
}
if(res==-1) {
val[p]+=X[i]-X[j];
swap(i,j);
continue;
}
res-=1;
val[p]+=X[j]-X[res];
val[p]+=X[i]-X[res];
j=res;
swap(i,j);
}
assert(make_pair(pi,pj)!=make_pair(i,j));
}
val[p]-=X[N]-X[1];
i=p;
}
cin>>Q;
for(int i=1;i<=Q;i++) {
int x;
cin>>x;
auto it=lower_bound(X+1,X+N+1,x)-X;
if(X[it]-x<x-X[it-1]) {
cout<<val[it]+X[it]-x<<'\n';
} else {
cout<<val[it-1]+x-X[it-1]<<'\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Execution timed out |
3095 ms |
4444 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Execution timed out |
3095 ms |
4444 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 3 |
Execution timed out |
3048 ms |
4444 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Execution timed out |
3095 ms |
4444 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
