#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 == S.end()) --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]){
if(wsk < n) update(wsk, {oo, 0}, 0);
update(wsk, {nxt[wsk][1], a[wsk]}, 1);
wsk++;
}
if(x == a[wsk] || x < a[1])
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 = max(x, a[1]), r = min(x, a[n]), act = x;
ll res = 0;
bool strona = 0;
if(x-a[wsk-1] <= a[wsk]-x){
l = a[wsk-1];
act = l;
res += x - a[wsk-1];
strona ^=1;
}
else{
r = a[wsk];
act = r;
res += a[wsk]-x;
}
while(l > a[1] || r < a[n]){
pair<int, int> tmp;
if(!strona){
tmp = leftquery(1, 0, BASE-1, l);
if(l != tmp.first){
//cout << tmp.first << " " << tmp.second << "\n";
res += abs(tmp.second-act);
res += abs(tmp.second - tmp.first);
act = tmp.first;
r = max({r, tmp.first, tmp.second});
l = min({l, tmp.second, tmp.first});
}
}
else{
tmp = rightquery(1, 0, BASE-1, r);
if(r != tmp.first){
res += abs(tmp.second-act);
res += abs(tmp.second - tmp.first);
act = tmp.first;
r = max({r, tmp.first, tmp.second});
l = min({l, tmp.second, tmp.first});
}
}
//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";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
13416 KB |
Output is correct |
2 |
Correct |
30 ms |
13620 KB |
Output is correct |
3 |
Correct |
29 ms |
13636 KB |
Output is correct |
4 |
Correct |
29 ms |
13636 KB |
Output is correct |
5 |
Correct |
29 ms |
13660 KB |
Output is correct |
6 |
Correct |
31 ms |
13492 KB |
Output is correct |
7 |
Correct |
29 ms |
13648 KB |
Output is correct |
8 |
Correct |
31 ms |
13520 KB |
Output is correct |
9 |
Incorrect |
28 ms |
13404 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
13416 KB |
Output is correct |
2 |
Correct |
30 ms |
13620 KB |
Output is correct |
3 |
Correct |
29 ms |
13636 KB |
Output is correct |
4 |
Correct |
29 ms |
13636 KB |
Output is correct |
5 |
Correct |
29 ms |
13660 KB |
Output is correct |
6 |
Correct |
31 ms |
13492 KB |
Output is correct |
7 |
Correct |
29 ms |
13648 KB |
Output is correct |
8 |
Correct |
31 ms |
13520 KB |
Output is correct |
9 |
Incorrect |
28 ms |
13404 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
13404 KB |
Output is correct |
2 |
Correct |
28 ms |
13516 KB |
Output is correct |
3 |
Correct |
28 ms |
13404 KB |
Output is correct |
4 |
Incorrect |
28 ms |
13396 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
13416 KB |
Output is correct |
2 |
Correct |
30 ms |
13620 KB |
Output is correct |
3 |
Correct |
29 ms |
13636 KB |
Output is correct |
4 |
Correct |
29 ms |
13636 KB |
Output is correct |
5 |
Correct |
29 ms |
13660 KB |
Output is correct |
6 |
Correct |
31 ms |
13492 KB |
Output is correct |
7 |
Correct |
29 ms |
13648 KB |
Output is correct |
8 |
Correct |
31 ms |
13520 KB |
Output is correct |
9 |
Incorrect |
28 ms |
13404 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |