#include "bits/stdc++.h"
#define int long long
using namespace std;
struct segtree_partial {
vector<int> st;
int stok;
void u(int l, int r, int tar, int idx, int val) {
if(l == r) {
st[idx] = val;
return;
}
int mid = (l+r) >> 1;
if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
else u(mid+1, r, tar, 2*idx+2, val);
st[idx] = max(st[2*idx+1], st[2*idx+2]);
}
int qu1(int l, int r, int constl, int constr, int idx, int val) { // Last element in [l, r] > v
if(l <= constl && constr <= r) {
if(st[idx] <= val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
if(st[2*idx+2] > val) idx = 2*idx+2, constl = mid+1;
else idx = 2*idx+1, constr = mid;
}
return constl;
}
int mid = (constl + constr) >> 1;
if(mid < l || r < constl) return qu1(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid+1) return qu1(l, r, constl, mid, 2*idx+1, val);
else {
int rchi = qu1(l, r, mid+1, constr, 2*idx+2, val);
if(rchi != -1) return rchi;
return qu1(l, r, constl, mid, 2*idx+1, val);
}
}
int qu2(int l, int r, int constl, int constr, int idx, int val) { // First element in [l, r] > v
if(l <= constl && constr <= r) {
if(st[idx] <= val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
if(st[2*idx+1] > val) idx = 2*idx+1, constr = mid;
else idx = 2*idx+2, constl = mid+1;
}
return constl;
}
int mid = (constl + constr) >> 1;
if(mid < l || r < constl) return qu2(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid+1) return qu2(l, r, constl, mid, 2*idx+1, val);
else {
int lchi = qu2(l, r, constl, mid, 2*idx+1, val);
if(lchi != -1) return lchi;
return qu2(l, r, mid+1, constr, 2*idx+2, val);
}
}
void resize(int k) {
stok = k;
st.resize(4*k + 10);
}
void upd(int i, int v) { u(0, stok, i, 0, v); }
int last_greater(int l, int r, int v) { return qu1(l, r, 0, stok, 0, v); }
int first_greater(int l, int r, int v) { return qu2(l, r, 0, stok, 0, v); }
};
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int x[n+1];
for(int i=1; i<=n; i++) cin >> x[i];
segtree_partial y, z;
y.resize(n);
z.resize(n);
for(int i=2; i<=n; i++) y.upd(i, 2*x[i]-x[i-1]);
for(int i=1; i<n; i++) z.upd(i, x[i+1]-2*x[i]);
int q;
cin >> q;
while(q--) {
int s;
cin >> s;
int ll=1, rr=n;
while(ll<rr) {
int mid = (ll+rr+1)>>1;
if(x[mid] <= s) ll=mid;
else rr=mid-1;
}
int ans = 0;
int cur;
int mn = 1e18;
for(int i=max(1ll, ll-2); i<=min(n, ll+2); i++) {
if(abs(x[i] - s) < mn) {
mn = abs(x[i] - s);
cur = i;
}
}
ans += abs(x[cur] - s);
int l=cur, r=cur;
while(l!=1 || r!=n) {
if(l == 1) {
ans += x[n] - x[cur];
break;
}
else if(r == n) {
ans += x[cur] - x[1];
break;
}
else if(l == cur) {
int i = y.last_greater(2, l, x[r+1]);
if(i != -1) {
ans += x[cur] - x[i];
ans += x[r+1] - x[i];
r++;
l = i;
cur = r;
}
else {
ans += x[cur] - x[1];
ans += x[n] - x[1];
break;
}
}
else {
int i = z.first_greater(r, n-1, -x[l-1] - 1);
if(i != -1) {
ans += x[i] - x[cur];
ans += x[i] - x[l-1];
l--;
r = i;
cur = l;
}
else {
ans += x[n] - x[cur];
ans += x[n] - x[1];
break;
}
}
}
cout << ans << "\n";
}
}
Compilation message
travel.cpp: In function 'int32_t main()':
travel.cpp:102:12: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
102 | else if(r == n) {
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
63 ms |
14816 KB |
Output is correct |
18 |
Correct |
63 ms |
14824 KB |
Output is correct |
19 |
Correct |
63 ms |
15904 KB |
Output is correct |
20 |
Correct |
55 ms |
15220 KB |
Output is correct |
21 |
Correct |
55 ms |
15032 KB |
Output is correct |
22 |
Correct |
86 ms |
16048 KB |
Output is correct |
23 |
Correct |
69 ms |
15768 KB |
Output is correct |
24 |
Correct |
58 ms |
15440 KB |
Output is correct |
25 |
Correct |
59 ms |
15736 KB |
Output is correct |
26 |
Correct |
53 ms |
15624 KB |
Output is correct |
27 |
Correct |
84 ms |
14924 KB |
Output is correct |
28 |
Correct |
55 ms |
15772 KB |
Output is correct |
29 |
Correct |
53 ms |
14872 KB |
Output is correct |
30 |
Correct |
53 ms |
14820 KB |
Output is correct |
31 |
Correct |
55 ms |
15416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
222 ms |
18040 KB |
Output is correct |
8 |
Correct |
217 ms |
18036 KB |
Output is correct |
9 |
Correct |
174 ms |
17892 KB |
Output is correct |
10 |
Correct |
197 ms |
18144 KB |
Output is correct |
11 |
Correct |
180 ms |
18016 KB |
Output is correct |
12 |
Correct |
182 ms |
17856 KB |
Output is correct |
13 |
Correct |
43 ms |
3068 KB |
Output is correct |
14 |
Correct |
32 ms |
1336 KB |
Output is correct |
15 |
Correct |
172 ms |
16588 KB |
Output is correct |
16 |
Correct |
201 ms |
18768 KB |
Output is correct |
17 |
Correct |
212 ms |
19144 KB |
Output is correct |
18 |
Correct |
46 ms |
3788 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
63 ms |
14816 KB |
Output is correct |
18 |
Correct |
63 ms |
14824 KB |
Output is correct |
19 |
Correct |
63 ms |
15904 KB |
Output is correct |
20 |
Correct |
55 ms |
15220 KB |
Output is correct |
21 |
Correct |
55 ms |
15032 KB |
Output is correct |
22 |
Correct |
86 ms |
16048 KB |
Output is correct |
23 |
Correct |
69 ms |
15768 KB |
Output is correct |
24 |
Correct |
58 ms |
15440 KB |
Output is correct |
25 |
Correct |
59 ms |
15736 KB |
Output is correct |
26 |
Correct |
53 ms |
15624 KB |
Output is correct |
27 |
Correct |
84 ms |
14924 KB |
Output is correct |
28 |
Correct |
55 ms |
15772 KB |
Output is correct |
29 |
Correct |
53 ms |
14872 KB |
Output is correct |
30 |
Correct |
53 ms |
14820 KB |
Output is correct |
31 |
Correct |
55 ms |
15416 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
222 ms |
18040 KB |
Output is correct |
39 |
Correct |
217 ms |
18036 KB |
Output is correct |
40 |
Correct |
174 ms |
17892 KB |
Output is correct |
41 |
Correct |
197 ms |
18144 KB |
Output is correct |
42 |
Correct |
180 ms |
18016 KB |
Output is correct |
43 |
Correct |
182 ms |
17856 KB |
Output is correct |
44 |
Correct |
43 ms |
3068 KB |
Output is correct |
45 |
Correct |
32 ms |
1336 KB |
Output is correct |
46 |
Correct |
172 ms |
16588 KB |
Output is correct |
47 |
Correct |
201 ms |
18768 KB |
Output is correct |
48 |
Correct |
212 ms |
19144 KB |
Output is correct |
49 |
Correct |
46 ms |
3788 KB |
Output is correct |
50 |
Correct |
419 ms |
20348 KB |
Output is correct |
51 |
Correct |
315 ms |
20204 KB |
Output is correct |
52 |
Correct |
254 ms |
20300 KB |
Output is correct |
53 |
Correct |
269 ms |
18608 KB |
Output is correct |
54 |
Correct |
302 ms |
20388 KB |
Output is correct |
55 |
Correct |
299 ms |
20416 KB |
Output is correct |
56 |
Correct |
147 ms |
19580 KB |
Output is correct |
57 |
Correct |
160 ms |
19940 KB |
Output is correct |
58 |
Correct |
150 ms |
20280 KB |
Output is correct |