#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
struct SparseTable {
vector<vector<int> > ST;
int N, K;
SparseTable(int _N, int a[]): N(_N) {
K = MSB(N);
ST.resize(K);
ST[0] = vector<int>(a, a+N);
for (int k = 1; k < K; ++k)
for (int i = 0; i+(1<<k) <= N; ++i)
ST[k].push_back( min(ST[k-1][i], ST[k-1][i+(1<<(k-1))]) );
}
inline int MSB(unsigned int x) { return 32-__builtin_clz(x); }
int query(int x, int y) {
int k = MSB(y-x+1) - 1;
return min(ST[k][x], ST[k][y-(1<<k)+1]);
}
};
struct SparseTable2 {
vector<vector<int> > ST;
int N, K;
SparseTable2(int _N, int a[]): N(_N) {
K = MSB(N);
ST.resize(K);
ST[0] = vector<int>(a, a+N);
for (int k = 1; k < K; ++k)
for (int i = 0; i+(1<<k) <= N; ++i)
ST[k].push_back( max(ST[k-1][i], ST[k-1][i+(1<<(k-1))]) );
}
inline int MSB(unsigned int x) { return 32-__builtin_clz(x); }
int query(int x, int y) {
int k = MSB(y-x+1) - 1;
return max(ST[k][x], ST[k][y-(1<<k)+1]);
}
};
void solve(){
int n;
cin >> n;
int arr[n+5];
for(int x=1;x<=n;x++){
cin >> arr[x];
}
arr[0]=INT_MIN;
arr[n+1]=1e15;
int r[n+5];
int l[n+5];
for(int x=1;x<=n;x++){
l[x]=2*arr[x]-arr[x-1];
r[x]=2*arr[x]-arr[x+1];
}
SparseTable2 st(n+2,l);
SparseTable st2(n+2,r);
int q;
cin >> q;
for(int x=0;x<q;x++){
int index;
cin >> index;
int cur=0;
int hold=lower_bound(arr,arr+n+2,index)-arr;
if(index-arr[hold-1]<=arr[hold]-index) cur=hold-1;
else cur=hold;
int counter=abs(index-arr[cur]);
bool amos=true;
if(arr[cur]-arr[cur-1]<=arr[cur+1]-arr[cur]) amos=false;
int left=cur;
int right=cur;
while(left>1&&right<n){
if(amos){
//venture right
int target=arr[left-1];
//modify
//for(int y=cur+1;y<=n;y++){
//right=y;
//if(r[y]<=target) break;
//}
int lft=cur+1;
int rgt=n;
int mid;
int best=rgt;
while(lft<=rgt){
//show2(lft,lft,rgt,rgt);
mid=(lft+rgt)/2;
if(st2.query(cur+1,mid)<=target){
best=mid;
rgt=mid-1;
}
else lft=mid+1;
}
right=best;
//modify
counter+=abs(arr[left-1]-arr[right]);
counter+=abs(arr[right]-arr[cur]);
cur=left-1;
left--;
amos=false;
}
else{
//venture left
int target=arr[right+1];
//modify
//for(int y=cur-1;y>=1;y--){
//left=y;
//if(l[y]>target) break;
//}
int lft=1;
int rgt=cur-1;
int mid;
int best=lft;
while(lft<=rgt){
//show2(lft,lft,rgt,rgt);
mid=(lft+rgt)/2;
if(st.query(mid,cur-1)>target){
best=mid;
lft=mid+1;
}
else rgt=mid-1;
}
left=best;
//modify
counter+=abs(arr[left]-arr[right+1]);
counter+=abs(arr[left]-arr[cur]);
cur=right+1;
right++;
amos=true;
}
}
if(left!=1){
counter+=abs(arr[cur]-arr[1]);
}
if(right!=n){
counter+=abs(arr[cur]-arr[n]);
}
cout << counter << "\n";
}
}
/*
10
1 2 3 4 5 6 7 8 9 10
1
2
*/
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
680 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
680 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
62 ms |
59368 KB |
Output is correct |
18 |
Correct |
62 ms |
59512 KB |
Output is correct |
19 |
Correct |
63 ms |
59480 KB |
Output is correct |
20 |
Correct |
64 ms |
59512 KB |
Output is correct |
21 |
Correct |
61 ms |
59500 KB |
Output is correct |
22 |
Correct |
63 ms |
59528 KB |
Output is correct |
23 |
Correct |
61 ms |
59468 KB |
Output is correct |
24 |
Correct |
61 ms |
59524 KB |
Output is correct |
25 |
Correct |
61 ms |
59372 KB |
Output is correct |
26 |
Correct |
61 ms |
59480 KB |
Output is correct |
27 |
Correct |
66 ms |
59728 KB |
Output is correct |
28 |
Correct |
63 ms |
59480 KB |
Output is correct |
29 |
Correct |
63 ms |
59348 KB |
Output is correct |
30 |
Correct |
60 ms |
59476 KB |
Output is correct |
31 |
Correct |
63 ms |
59324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 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 |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
122 ms |
61004 KB |
Output is correct |
8 |
Correct |
124 ms |
64216 KB |
Output is correct |
9 |
Correct |
125 ms |
63336 KB |
Output is correct |
10 |
Correct |
124 ms |
63308 KB |
Output is correct |
11 |
Correct |
122 ms |
63304 KB |
Output is correct |
12 |
Correct |
128 ms |
63416 KB |
Output is correct |
13 |
Correct |
31 ms |
4188 KB |
Output is correct |
14 |
Correct |
23 ms |
1620 KB |
Output is correct |
15 |
Incorrect |
139 ms |
64332 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
680 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
62 ms |
59368 KB |
Output is correct |
18 |
Correct |
62 ms |
59512 KB |
Output is correct |
19 |
Correct |
63 ms |
59480 KB |
Output is correct |
20 |
Correct |
64 ms |
59512 KB |
Output is correct |
21 |
Correct |
61 ms |
59500 KB |
Output is correct |
22 |
Correct |
63 ms |
59528 KB |
Output is correct |
23 |
Correct |
61 ms |
59468 KB |
Output is correct |
24 |
Correct |
61 ms |
59524 KB |
Output is correct |
25 |
Correct |
61 ms |
59372 KB |
Output is correct |
26 |
Correct |
61 ms |
59480 KB |
Output is correct |
27 |
Correct |
66 ms |
59728 KB |
Output is correct |
28 |
Correct |
63 ms |
59480 KB |
Output is correct |
29 |
Correct |
63 ms |
59348 KB |
Output is correct |
30 |
Correct |
60 ms |
59476 KB |
Output is correct |
31 |
Correct |
63 ms |
59324 KB |
Output is correct |
32 |
Correct |
0 ms |
344 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
344 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
122 ms |
61004 KB |
Output is correct |
39 |
Correct |
124 ms |
64216 KB |
Output is correct |
40 |
Correct |
125 ms |
63336 KB |
Output is correct |
41 |
Correct |
124 ms |
63308 KB |
Output is correct |
42 |
Correct |
122 ms |
63304 KB |
Output is correct |
43 |
Correct |
128 ms |
63416 KB |
Output is correct |
44 |
Correct |
31 ms |
4188 KB |
Output is correct |
45 |
Correct |
23 ms |
1620 KB |
Output is correct |
46 |
Incorrect |
139 ms |
64332 KB |
Output isn't correct |
47 |
Halted |
0 ms |
0 KB |
- |