#include<bits/stdc++.h>
using namespace std ;
#define maxn 200009
#define ll long long
#define fi first
#define se second
#define pb push_back
#define left id<<1
#define right id<<1|1
#define re exit(0);
const int mod = 1e9+7 ;
const int INF = 1e9+1 ;
const int LOG = 18 ;
typedef vector<int> vi ;
typedef vector<ll> vl ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
typedef pair<ll,ll> pll ;
void add ( int &a , int b )
{
a += b ;
if ( a < 0 ) a += mod ;
if ( a >= mod ) a -= mod ;
}
template < typename T > void chkmin (T &a , T b) { if (a>b) a=b ;}
template < typename T > void chkmax (T &a , T b) { if (a<b) a=b ;}
void rf ()
{
freopen ("bai1.inp","r",stdin) ;
// freopen ("bai1.out","w",stdout) ;
}
int _pow ( int a , int n )
{
if ( n == 0 ) return 1 ;
int res = _pow(a,n/2) ;
if ( n % 2 ) return (1ll*res*res%mod*a%mod) ;
else return 1ll*res*res%mod ;
}
int n , nq ;
int a [maxn] ;
int query [maxn] ;
void sub1 ()
{
set <int> S ;
for ( int i = 1 ; i <= n ; i ++ ) S.insert(a[i]) ;
ll res = 0 ;
int pos = query [1] ;
while ( true )
{
int des = 2*INF ;
auto it = S.lower_bound(pos) ;
if ( it!=S.end() && *it - pos < des - pos ) des = *it ;
if ( it!=S.begin() && pos - *(--it) <= des - pos ) des = *it ;
res += abs (des-pos) ;
pos = des ;
S.erase(pos) ;
if ( S.empty() ) break ;
}
cout << res ;
}
bool check_sub2 ()
{
for ( int i = 2 ; i <= n ; i ++ ) if ( a [i] - a [i-1] > 100 ) return false ;
return true ;
}
void sub2 ()
{
set <int> S ;
map <int,int> position ;
for ( int i = 1 ; i <= n ; i ++ ) S.insert (a[i]) , position [a[i]] = i ;
for ( int run = 1 ; run <= nq ; run ++ )
{
int x = query [run] , up , down ;
auto it = S.lower_bound (x) ;
if ( it != S.end () ) up = *it ; else up = INF ;
if ( it != S.begin() ) down = *(--it) ; else down = -INF ;
ll res = 0 ;
if ( up == INF ) res += x - down , x = down ;
else res += up - x , x = up ;
int l = position [x] , r = position [x] ;
x = l ;
if ( x == 1 || x == n )
{
cout << res + a [n] - a [1] << "\n" ;
continue ;
}
while ( true )
{
if ( l == 1 || r == n ) break ;
if ( abs (a[l-1]-a[x]) <= abs (a[r+1]-a[x]) )
{
res += abs (a[l-1]-a[x]) ;
x = -- l ;
}
else
{
res += abs (a[r+1]-a[x]) ;
x = ++ r ;
}
}
if ( x == l ) res += abs (a[x]-a[1]) + a [n] - a [1] ;
else res += abs (a[x]-a[n]) + a [n] - a [1] ;
cout << res << "\n" ;
}
}
int main ()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ; cout.tie(0) ;
// rf () ;
cin >> n ;
for ( int i = 1 ; i <= n ; i ++ ) cin >> a [i] ;
cin >> nq ;
for ( int i = 1 ; i <= nq ; i ++ ) cin >> query [i] ;
sub2 () ; re
if ( nq == 1 ) sub1 () ;
else if ( check_sub2 () ) sub2 () ;
}
Compilation message
travel.cpp: In function 'void rf()':
travel.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | freopen ("bai1.inp","r",stdin) ;
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Execution timed out |
3086 ms |
21020 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
