Submission #984887

#TimeUsernameProblemLanguageResultExecution timeMemory
984887vjudge2Bitaro's travel (JOI23_travel)C++17
100 / 100
424 ms72364 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 200001; const int lg = 19; int lg2[N], mn[N][lg], mx[N][lg]; int query_min(int l, int r) { int j = lg2[r - l + 1]; return min(mn[l][j], mn[r - (1 << j) + 1][j]); } int query_max(int l, int r) { int j = lg2[r - l + 1]; return max(mx[l][j], mx[r - (1 << j) + 1][j]); } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n; vector<int> x(n), ll(n), rr(n); for (int i = 0; i < n; i++) { cin >> x[i]; ll[i] = rr[i] = i; } for (int i = 1; i < n; i++) { int dist = x[i] - x[i - 1]; int l = i, r = n - 1; while (l < r) { int mid = (l + r + 1) / 2; if (x[mid] - x[i] < dist) l = mid; else r = mid - 1; } if (x[l] - x[i] < dist) rr[i - 1] = l; // if i'm going left to i - 1, rb must > l } for (int i = 0; i < n - 1; i++) { int dist = x[i + 1] - x[i]; int l = 0, r = i; while (l < r) { int mid = (l + r) / 2; if (x[i] - x[mid] <= dist) r = mid; else l = mid + 1; } if (x[i] - x[l] <= dist) ll[i + 1] = l; // if i'm going right to i + 1, lb must < l } // for (int i = 0; i < n; i++) cout << ll[i] << ' ' << rr[i] << '\n'; // lg2[1] = 0; for (int i = 2; i <= n; i++) lg2[i] = lg2[i / 2] + 1; for (int i = 0; i < n; i++) mx[i][0] = rr[i], mn[i][0] = ll[i]; for (int j = 1; j < lg; j++) { for (int i = 0; i + (1 << j) - 1 < n; i++) { mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]); mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]); } } cin >> q; while (q--) { int s, ans = 0; cin >> s; int left = 0, lb, rb, cp; if (s >= x.back()) left = 1, lb = rb = n - 1, ans += s - x.back(), cp = n - 1; else if (s > x.front()) { auto it = lower_bound(x.begin(), x.end(), s); int prv, nxt; if ((*it) == s) { prv = *prev(it); nxt = *next(it); lb = rb = cp = it - x.begin(); } else { prv = *prev(it); nxt = *it; if (s - prv <= nxt - s) lb = rb = cp = it - x.begin() - 1, ans += s - prv; else lb = rb = cp = it - x.begin(), ans += nxt - s; } if (lb == 0) left = 1; else if (rb == n - 1) left = 0; else { prv = x[lb - 1]; nxt = x[rb + 1]; if (x[cp] - prv <= nxt - x[cp]) left = 0; else left = 1; } } else lb = rb = 0, ans += x.front() - s, cp = 0; // cout << "ans:" << lb << ' ' << rb << ' ' << ans << '\n'; for (int ti = 0; ti < (lg << 1); ti++) { left ^= 1; if (lb <= 0 && rb > n) break; if (left && lb > 0) { int l = 0, r = lb - 1; while (l < r) { int mid = (l + r) / 2; if (rb >= query_max(mid, lb - 1)) r = mid; else l = mid + 1; } ans += abs(x[cp] - x[l]); lb = cp = l; // cout << "ans:" << lb << ' ' << rb << ' ' << ans << '\n'; } else if (!left && rb < n - 1) { int l = rb + 1, r = n - 1; while (l < r) { int mid = (l + r + 1) / 2; if (lb <= query_min(rb + 1, mid)) l = mid; else r = mid - 1; } ans += abs(x[l] - x[cp]); rb = cp = l; // cout << "ans:" << lb << ' ' << rb << ' ' << ans << '\n'; } // cout << "iter\n"; } // cout << "final ans:" << lb << ' ' << rb << ' ' << ans << '\n'; cout << ans << '\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...