Submission #1213764

#TimeUsernameProblemLanguageResultExecution timeMemory
1213764jerzykBitaro's travel (JOI23_travel)C++20
100 / 100
222 ms8312 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define st first #define nd second typedef long long ll; typedef long double ld; const ll I = 1'000'000'000'000'000'000LL; const int II = 2'000'000'000; const ll M = 1'000'000'007LL; const int N = 1<<18; ll tab[N]; int drzmi[2 * N], drzma[2 * N]; int GetL(int v, int x) { v += N; while(v > 1) { if(v % 2 == 1 && drzma[v - 1] > x) {--v; break;} v /= 2; } //if(v == 1) return -1; while(v < N) { v *= 2; if(drzma[v + 1] >= x) ++v; } return v - N; } int GetR(int v, int x) { v += N; while(v > 1) { if(v % 2 == 0 && drzmi[v + 1] <= x) {++v; break;} v /= 2; } //if(v == 1) return -1; while(v < N) { v *= 2; ++v; if(drzmi[v - 1] <= x) --v; } return v - N; } ll Query(int n, ll s) { ll ans = 0LL; int cur = (lower_bound(tab + 1, tab + 1 + n, s) - tab); if(tab[cur] - s >= s - tab[cur - 1]) --cur; ans = tab[cur] - s; if(ans < 0) ans *= -1LL; int l = cur, r = cur, a; while(l != 1 || r != n) { // cout << "Q: " << l << " " << r << " " << cur << "\n"; // cout << tab[l - 1] << " " << tab[r + 1] << "\n"; if(tab[cur] - tab[l - 1] <= tab[r + 1] - tab[cur]) { // cout << "L:\n"; a = GetL(l, tab[r + 1]); ans += tab[cur] - tab[a]; l = a; cur = a; }else { // cout << "R:\n"; a = GetR(r, tab[l - 1]); ans += tab[a] - tab[cur]; r = a; cur = a; } } return ans; } void Solve() { int n, q, a; cin >> n; for(int i = 1; i <= n; ++i) cin >> tab[i]; tab[n + 1] = II + 100; tab[0] = -II; drzmi[n + N] = -II - 300; for(int i = 1; i < n; ++i) drzmi[i + N] = tab[i] - (tab[i + 1] - tab[i]); drzma[1 + N] = II + 300; for(int i = 2; i <= n; ++i) drzma[i + N] = tab[i] + (tab[i] - tab[i - 1]); for(int v = N - 1; v >= 1; --v) { drzmi[v] = min(drzmi[v * 2], drzmi[v * 2 + 1]); drzma[v] = max(drzma[v * 2], drzma[v * 2 + 1]); } cin >> q; for(int i = 1; i <= q; ++i) { cin >> a; ll ans = 0LL; ans = Query(n, a); cout << ans << "\n"; } } int main() { for(int i = 1; i < 2 * N; ++i) drzmi[i] = II; for(int i = 1; i < 2 * N; ++i) drzma[i] = -II; ios_base::sync_with_stdio(false); cin.tie(nullptr); //int t; cin >> t; //while(t--) Solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...