This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5;
int v[N];
int n;
int lb(int nr){
int l = 0,r = n;
while(l != r){
int mij = (l + r)/2;
if(v[mij] >= nr)r = mij;
else l = mij + 1;
}
return l;
}
int main(){
cin>>n;
for(int i = 0;i < n;i++){
cin>>v[i];
}
int q;
cin>>q;
for(int i = 0;i < q;i++){
int x;
cin>>x;
ll ans = 0;
int l,r,pos;
int tmp;
tmp = lb(x);
if(tmp != 0 && (tmp == n || x - v[tmp - 1] <= v[tmp] - x)){
ans+=x - v[tmp - 1];
l = tmp - 1;r = tmp - 1;
}else{
ans+=v[tmp] - x;
l = tmp;r = tmp;
}
pos = 0;
while(l != 0 || r != n - 1){
if(l == 0 || r == n - 1){
///go to n - 1
ans+=v[n - 1] - v[0];
l = 0;
r = n - 1;
continue;
}
if(pos == 0){
tmp = lb(v[l] - (v[r + 1] - v[l]));
if(tmp == l){
///bad go to r + 1
pos = 1;
ans+=v[r + 1] - v[l];
r++;
}else{
pos = 0;
ans+=v[l] - v[tmp];
l = tmp;
}
}else{
tmp = lb(v[r] + (v[r] - v[l - 1])) - 1;
if(tmp == r){
pos = 0;
ans+=v[r] - v[l - 1];
l--;
}else{
pos = 1;
ans+=v[tmp] - v[r];
r = tmp;
}
}
}
cout<<ans<<'\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |