#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int BASE = 1 << 18;
constexpr int oo = 2e9;
pair<int, int> TREE[BASE<<1][2]; //0 to z lewej/ 1 z prawej
set<int> S;
vector<pair<int, int>> queries;
ll ans[BASE];
int nxt[BASE][2]; //0 to z lewej/ 1 z prawej
int a[BASE];
int n, q;
void update(int v, pair<int, int> val, bool c){
v += BASE;
TREE[v][c] = val;
v/=2;
while(v > 0){
if(!c) TREE[v][c] = min(TREE[2*v][c], TREE[2*v+1][c]);
else TREE[v][c] = max(TREE[2*v][c], TREE[2*v+1][c]);
v/=2;
}
}
void compute(){
//z lewej
for(int i = 1; i < n; i++){
int roznica = a[i+1] - a[i];
auto it = S.lower_bound((a[i]-roznica));
nxt[i][0] = (*it);
}
nxt[n][0] = a[1];
//z prawej
for(int i = n; i > 1; i--){
int roznica = a[i] - a[i-1];
auto it = S.lower_bound((a[i]+roznica-1));
if((*it) >= a[i]+roznica) --it;
nxt[i][1] = (*it);
}
nxt[1][1] = a[n];
nxt[0][0] = oo;
for(int i = n+1; i < BASE; i++)
nxt[i][0] = oo;
for(int i = 0; i < BASE; i++)
update(i, {nxt[i][0], a[i]}, 0);
}
int wsk = 1;
void przesun(int x){
while(x > a[wsk]){
update(wsk, {oo, 0}, 0);
update(wsk, {nxt[wsk][1], a[wsk]}, 1);
wsk++;
}
if(x == a[wsk])
update(wsk, {nxt[wsk][1], a[wsk]}, 1);
}
pair<int, int> leftquery(int v, int l, int r, int x){ //chcemy sc jak najbardziej w lewo
if(l == r) return TREE[v][0];
int mid = (l+r)/2;
if(TREE[2*v][0].first < x || TREE[2*v][0].first == a[1])
return leftquery(2*v, l, mid, x);
return leftquery(2*v+1, mid+1, r, x);
}
pair<int, int> rightquery(int v, int l, int r, int x){ // chcemy isc jak najbardziej w prawo
if(l == r) return TREE[v][1];
int mid = (l+r)/2;
if(TREE[2*v+1][1].first > x || TREE[2*v+1][1].first == a[n])
return rightquery(2*v+1, mid+1, r, x);
return rightquery(2*v, l, mid, x);
}
ll check(int x){
int l = x, r = x, act = x;
ll res = 0;
if(x-a[wsk-1] <= a[wsk]-x){
l = a[wsk-1];
act = l;
res += x - a[wsk-1];
}
else{
r = a[wsk];
act = r;
res += a[wsk]-x;
}
//cout << "x " << x << "\n";
bool strona = 0;
while(l > a[1] || r < a[n]){
pair<int, int> tmp;
if(!strona){
tmp = leftquery(1, 0, BASE-1, l);
res += abs(tmp.second-act);
res += abs(tmp.second - tmp.first);
act = tmp.first;
r = max(r, tmp.second);
l = min(l, tmp.first);
}
else{
tmp = rightquery(1, 0, BASE-1, r);
res += abs(tmp.second-act);
res += abs(tmp.second - tmp.first);
act = tmp.first;
r = max(r, tmp.first);
l = min(l, tmp.second);
}
//cout << "l : " << l << " r: " << r << " RES : " << res << "\n";
strona ^= 1;
}
//cout << "\n";
return res;
}
void solve(){
for(auto [u, idx] : queries){
przesun(u);
ans[idx] = check(u);
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
a[0] = -oo;
for(int i = 1; i <= n; i++){
cin >> a[i];
S.insert(a[i]);
}
a[n+1] = oo;
compute();
cin >> q;
for(int i = 1; i <= q; i++){
int x;
cin >> x;
queries.push_back({x, i});
}
sort(queries.begin(), queries.end());
/*
for(int i = 1; i <= n; i++)
cout << nxt[i][0] << " ";
cout << "\n";
for(int i = 1; i <= n; i++)
cout << nxt[i][1] << " ";
cout << "\n";
*/
solve();
for(int i = 1; i <= q; i++)
cout << ans[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
13660 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
13644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
13660 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
13644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
13560 KB |
Output is correct |
| 2 |
Correct |
28 ms |
13404 KB |
Output is correct |
| 3 |
Correct |
29 ms |
13536 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
13396 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
13660 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
13644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
