Submission #415916

#TimeUsernameProblemLanguageResultExecution timeMemory
415916meatrowSnowball (JOI21_ho_t2)C++17
100 / 100
1142 ms13716 KiB
// #pragma GCC target ("avx2") // #pragma GCC optimization ("O3") #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int MOD = 1e9 + 7; ll binpow(ll a, ll p, int mod = MOD) { ll res = 1; while (p) { if (p & 1) { (res *= a) %= mod; } p >>= 1; (a *= a) %= mod; } return res; } ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } void solve() { int n, q; cin >> n >> q; vector<ll> x(n + 2); for (int i = 1; i <= n; i++) { cin >> x[i]; } x[0] = -1e18; x[n + 1] = 1e18; vector<ll> shift(q + 1); vector<ll> shiftR(q + 1); vector<ll> shiftL(q + 1); for (int i = 1; i <= q; i++) { ll w; cin >> w; shift[i] = shift[i - 1] + w; shiftR[i] = max(shift[i], shiftR[i - 1]); shiftL[i] = max(-shift[i], shiftL[i - 1]); } for (int i = 1; i <= n; i++) { ll ans = 0; { ll l = 0, r = min(x[i + 1] - x[i], shiftR.back()) + 1; while (r - l > 1) { ll mid = (l + r) / 2; int pos = lower_bound(shiftR.begin(), shiftR.end(), mid) - shiftR.begin(); if (x[i + 1] - x[i] - shiftL[pos] < mid) { r = mid; } else { l = mid; } } ans += l; } { ll l = 0, r = min(x[i] - x[i - 1], shiftL.back()) + 1; while (r - l > 1) { ll mid = (l + r) / 2; int pos = lower_bound(shiftL.begin(), shiftL.end(), mid) - shiftL.begin(); if (x[i] - x[i - 1] - shiftR[pos] < mid) { r = mid; } else { l = mid; } } ans += l; } cout << ans << '\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; for (int tc = 1; tc <= T; tc++) { // cout << "Case #" << tc << ": "; solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...