Submission #963792

#TimeUsernameProblemLanguageResultExecution timeMemory
963792EJIC_B_KEDAXSnowball (JOI21_ho_t2)C++17
100 / 100
111 ms15440 KiB
#ifdef LOCAL #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> #ifndef LOCAL // #pragma GCC optimize("O3") // #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt") #endif using namespace std; using ll = long long; using ld = long double; #define x first #define y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() mt19937 mt(123); void solve(); void init(); int32_t main() { #ifndef LOCAL cin.tie(nullptr)->sync_with_stdio(false); #endif cout << fixed << setprecision(30); init(); int t = 1; // cin >> t; while (t--) { solve(); } } void init() {} const int N = 200200; ll x[N], w[N], mn[N], mx[N], ans[N]; void solve() { int n, q; cin >> n >> q; for (int i = 0; i < n; i++) { cin >> x[i]; } for (int i = 0; i < q; i++) { ll nw; cin >> nw; w[i + 1] = w[i] + nw; } for (int i = 1; i <= q; i++) { mn[i] = min(mn[i - 1], w[i]); mx[i] = max(mx[i - 1], w[i]); } for (int i = 0; i < n; i++) { if (i) { ll dist = x[i] - x[i - 1]; if (dist >= mx[q] - mn[q]) { ans[i] -= mn[q]; } else { int l = 0, r = q; while (r - l > 1) { int m = (r + l) / 2; if (mx[m] - mn[m] >= dist) { r = m; } else { l = m; } } if (mx[r] != mx[l]) { ans[i] -= mn[r]; } else { ans[i] += dist - mx[r]; } } } else { ans[i] -= mn[q]; } if (i + 1 < n) { ll dist = x[i + 1] - x[i]; if (dist >= mx[q] - mn[q]) { ans[i] += mx[q]; } else { int l = 0, r = q; while (r - l > 1) { int m = (r + l) / 2; if (mx[m] - mn[m] >= dist) { r = m; } else { l = m; } } if (r == q + 1 || mn[r] != mn[l]) { ans[i] += mx[r]; } else { ans[i] += dist + mn[r]; } } } else { ans[i] += mx[q]; } } for (int i = 0; i < n; i++) { cout << ans[i] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...