#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];
return min(spl[l][cur],spl[r-(1<<cur)+1][cur]);
}
int ask_right(int l,int r){
int cur=lg[r-l];
//cout <<"ask"<<" "<<l<<" "<<r<<" "<<max(spr[l][cur],spr[r-(1<<cur)+1][cur])<<endl;
//cout <<l<<" "<<r<<" "<<spr[1][cur]<<" "<<cur<<endl;
return max(spr[l][cur],spr[r-(1<<cur)+1][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]=nl[i];
//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) l=mid;
else r=mid;
}
nr[i]=tab[l];
spr[i][0]=nr[i];
//if(i==1000) cout <<tab[i]<<endl;
//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 <<spl[1000][0]<<" "<<nl[1000]<<endl;
//cout <<ask_left(1000,1000)<<endl;
int q;
cin>>q;
while(q--){
//out <<"nea"<<endl;
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-1]==x) test=true;
int cur;
if(tab[idx]-x<x-tab[idx-1-test]){
cur=1;
}else{
cur=0;
}
if(test) idx--;
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(idx,mid)>=lefty) l=mid;
else r=mid;
}
//cout <<idx<<" "<<nl[r]<<" "<<lefty<<" "<<ask_left(idx,r)<<endl;
ans+=tab[r]-lefty;
righty=tab[r];
idx=r;
cur=0;
}else{
int l=0;
int r=idx;
while(r-l>1){
int mid=(r+l)/2;
if(ask_right(mid,idx)<=righty) r=mid;
else l=mid;
//cout <<ask_right(649,idx)<<" "<<l<<" "<<r<<endl;
}
//cout <<l<<" "<<idx<<" "<<ask_right(1,idx)<<" "<<righty<<endl;
ans+=righty-tab[l];
lefty=tab[l];
idx=l;
cur=1;
}
//cout <<lefty<<" "<<righty<<endl;
//break;
}
//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 |
3928 KB |
Output is correct |
| 2 |
Execution timed out |
3013 ms |
4188 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3928 KB |
Output is correct |
| 2 |
Execution timed out |
3013 ms |
4188 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3932 KB |
Output is correct |
| 4 |
Correct |
1 ms |
3932 KB |
Output is correct |
| 5 |
Correct |
1 ms |
3932 KB |
Output is correct |
| 6 |
Correct |
1 ms |
3940 KB |
Output is correct |
| 7 |
Runtime error |
18 ms |
5880 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3928 KB |
Output is correct |
| 2 |
Execution timed out |
3013 ms |
4188 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
