Submission #918920

#TimeUsernameProblemLanguageResultExecution timeMemory
918920esomerBitaro's travel (JOI23_travel)C++17
0 / 100
1 ms600 KiB
#include <bits/stdc++.h> using namespace std; int msb[200001]; int getMax(int l, int r, vector<vector<int>>& dp){ int k = msb[r - l + 1]; return max(dp[k][r], dp[k][l + (1 << k) - 1]); } int getMin(int l, int r, vector<vector<int>>& dp){ int k = msb[r - l + 1]; return min(dp[k][r], dp[k][l + (1 << k) - 1]); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> X(n); for(auto &i : X) cin >> i; vector<vector<int>> goLeft(20, vector<int> (n, 2e9+1)); vector<vector<int>> goRight(20, vector<int> (n, -2e9-1)); for(int k = 0; k < 20; k++){ for(int i = 0; i < n; i++){ if(k == 0){ if(i == 0 || i == n - 1) continue; goLeft[k][i] = 2 * X[i] - X[i-1]; goRight[k][i] = 2 * X[i] - X[i+1]; }else{ if(i - (1 << (k-1)) < 0){ goLeft[k][i] = goLeft[k-1][i]; goRight[k][i] = goRight[k-1][i]; }else{ goLeft[k][i] = max(goLeft[k-1][i], goLeft[k-1][i-(1<<(k-1))]); goRight[k][i] = min(goRight[k-1][i], goRight[k-1][i-(1<<(k-1))]); } } } } int currExp = 1; int exp = -1; for(int i = 1; i <= n; i++){ if(i == currExp){ exp++; currExp *= 2; } msb[i] = exp; } int q; cin >> q; while(q--){ int x; cin >> x; int lo = 0; int hi = n - 1; int bst = -1; while(lo <= hi){ int mid = (lo + hi) / 2; if(X[mid] >= x){ bst = mid; hi = mid - 1; }else lo = mid + 1; } long long dist = 0; if(bst == -1){ dist = X[0] - x; x = 0; }else if(bst == n-1){ dist = x - X[n-1]; x = n - 1; }else{ if(x - X[bst] <= X[bst+1]-x){ dist = x - X[bst]; x = bst; }else{ dist = X[bst+1] - x; x = bst + 1; } } int l = x, r = x; while(l != 0 && r != n - 1){ if(X[x] - X[l - 1] <= X[r+1] - X[x]){ lo = 0; hi = l - 1; bst = -1; while(lo <= hi){ int mid = (lo + hi) / 2; if(getMax(mid, l - 1, goLeft) > X[r+1]){ bst = mid; lo = mid + 1; }else hi = mid - 1; } dist += X[x] - X[bst]; l = bst; x = bst; }else{ lo = r+1; hi = n - 1; bst = -1; while(lo <= hi){ int mid = (lo + hi) / 2; if(X[l-1] >= getMin(r+1, mid, goRight)){ bst = mid; hi = mid - 1; }else lo = mid + 1; } dist += X[bst] - X[x]; r = bst; x = bst; } } dist += X[n-1] - X[0]; cout << dist << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...