Submission #1210149

#TimeUsernameProblemLanguageResultExecution timeMemory
1210149dima2101Bitaro's travel (JOI23_travel)C++20
0 / 100
2 ms328 KiB
#include <bits/stdc++.h> #define int long long int give_sum(int l, int r, std::vector<int> &pref) { if (l > r) { return 0; } if (l == 0) { return pref[r]; } return pref[r] - pref[l - 1]; } signed main() { int n; std::cin >> n; std::vector<int> x(n); std::vector<int> pref(n); for (int i = 0; i < n; i++) { std::cin >> x[i]; } std::vector<int> prev(n); for (int i = 0; i < n; i++) { if (i == n - 1) { prev[i] = 0; continue; } int last = 0; for (int j = i; j >= 1; j--) { if (x[i + 1] - x[j] < x[j] - x[j - 1]) { last = j; break; } } // std::cout << i << ' ' << last << std::endl; prev[i] = last; } std::vector<int> next(n); for (int i = 0; i < n; i++) { if (i == 0) { next[i] = n - 1; continue; } int last = n - 1; for (int j = i; j < n - 1; j++) { if (x[j] - x[i - 1] <= x[j + 1] - x[j]) { last = j; break; } } // std::cout << i << ' ' << next[i] << ' ' << last << std::endl; next[i] = last; } // exit(0); std::vector<int> ans(n); for (int i = 0; i < n; i++) { int l = i, r = i; int j = i; while ((r - l + 1) != n) { //'std::cout << l << ' ' << r << ' ' << j << ' ' << next[j] << ' ' << prev[j] << std::endl; if (next[j] != j) { r = next[j]; ans[i] += x[r] - x[j]; j = r; } else { l = prev[j]; ans[i] += x[j] - x[l]; j = l; } } } int q; std::cin >> q; for (int i = 0; i < q; i++) { int now; std::cin >> now; int l = 0, r = x.size(); while (l + 1 < r) { int mid = (l + r) / 2; if (x[mid] <= now) { l = mid; } else { r = mid; } } int cur = 0; int now_ind = -1; if (r == x.size()) { cur += now - x.back(); now_ind = l; } else { if (std::abs(x[l] - now) <= std::abs(x[r] - now)) { now_ind = l; cur += std::abs(x[l] - now); } else { now_ind = r; cur += std::abs(x[r] - now); } } std::cout << ans[now_ind] + cur << std::endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...