#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define ve vector
#define ll long long
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define onbit __builtin_popcount
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll MOD = 1e9+7;
const int nax = 1e5+5;
const int MAX_VAL = 1e6+1;
double PI=3.14159265359;
int arx[8]={1,0,0,-1,-1,-1, 1, 1};
int ary[8]={0,1,-1, 0, 1,-1,-1, 1};
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
vector<int> tab(nax);
vector<int> nl(nax);
vector<int> nr(nax);
int lg[nax];
int spr[nax][18];
int spl[nax][18];
int ask_left(int l,int r){
int cur=lg[r-l+1];
return min(spl[l][cur],spl[r-(1<<cur)][cur]);
}
int ask_right(int l,int r){
int cur=lg[r-l+1]-1;
return max(spr[l][cur],spr[r-(1<<cur)][cur]);
}
int main(){
optimise;
//setIO("dec");
lg[1]=0;
for (int i = 2; i < nax; ++i)
{
lg[i]=lg[i/2]+1;
}
int n;
cin>>n;
tab.resize(n);
for (int i = 0; i < n; ++i)
{
cin>>tab[i];
}
nr[0]=tab[n-1];
nl[n-1]=tab[0];
spr[0][0]=nr[0];
spl[n-1][0]=nl[0];
for (int i = 0; i < n-1; ++i)
{
int cur=tab[i+1]-tab[i];
int l=-1;
int r=i;
while(r-l>1){
int mid=(r+l)/2;
if(tab[i]-tab[mid]>cur) l=mid;
else r=mid;
}
nl[i]=tab[r];
spl[i][0]=tab[r];
//cout <<nl[i]<<" ";
}//cout <<endl;
for (int i = n-1; i > 0; --i)
{
int cur=tab[i]-tab[i-1];
int l=i;
int r=n;
while(r-l>1){
int mid=(r+l)/2;
if(tab[mid]-tab[i]>=cur) r=mid;
else l=mid;
}
nr[i]=tab[l];
spr[i][0]=tab[l];
//cout <<nr[i]<<" ";
}//cout <<endl;
for (int i = 1; i < 18; ++i)
{
//cout <<"3asba"<<endl;
for (int j = 0; j+(1<<i) < n; ++j)
{
spl[j][i]=min(spl[j][i-1],spl[j+(1<<(i-1))][i-1]);
}
for (int j = 0; j+(1<<i)< n; j++)
{
spr[j][i]=max(spr[j][i-1],spr[j+(1<<(i-1))][i-1]);
}
}
//cout <<spr[0][0]<<endl;
int q;
cin>>q;
while(q--){
int x;
cin>>x;
long long ans=0;
if(x>=tab[n-1]){
cout <<x-tab[0]<<endl;
continue;
}else if(x<=tab[0]){
cout <<tab[n-1]-x<<endl;
continue;
}
int idx=upper_bound(tab.begin(),tab.end(),x)-tab.begin();
bool test=false;
if(tab[idx]==x) test=true;
int cur;
if(tab[idx]-x<x-tab[idx-1-test]){
cur=1;
}else{
cur=0;
}
int lefty=x;
int righty=x;
while(lefty>tab[0]&&righty<tab[n-1]){
//cout <<"new "<<lefty<<" "<<righty<<" "<<cur<<endl;
if(cur==1){
int l=idx;
int r=n-1;
while(r-l>1){
int mid=(r+l)/2;
if(ask_left(l,mid)>=lefty) l=mid;
else r=mid;
}
ans+=tab[r]-lefty;
righty=tab[r];
cur=0;
}else{
int l=0;
int r=idx;
while(r-l>1){
int mid=(r+l)/2;
if(ask_right(mid,r)<=righty) r=mid;
else l=mid;
}
//cout <<l<<" "<<r<<" "<<ask_right(l,r)<<endl;
ans+=righty-tab[l];
lefty=tab[l];
cur=1;
}
}
//cout <<ans<<" "<<lefty<<" "<<righty<<endl;
if(righty<tab[n-1]) ans+=tab[n-1]-lefty;
if(lefty>tab[0]) ans+=righty-tab[0];
cout << ans<<endl;
}
}
Compilation message
travel.cpp: In function 'void setIO(std::string)':
travel.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
travel.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4188 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4188 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4188 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4188 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3928 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3928 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 4 |
Correct |
1 ms |
3908 KB |
Output is correct |
| 5 |
Correct |
1 ms |
3932 KB |
Output is correct |
| 6 |
Correct |
1 ms |
3928 KB |
Output is correct |
| 7 |
Runtime error |
15 ms |
5844 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4188 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4188 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
