Submission #887383

#TimeUsernameProblemLanguageResultExecution timeMemory
887383viwlesxqDivide and conquer (IZhO14_divide)C++17
0 / 100
0 ms600 KiB
#include <bits/stdc++.h> using namespace std; typedef int64_t ll; #define all(x) x.begin(), x.end() #define size(x) (int)x.size() template<class S, class T> bool chmin(S &a, const T &b) { return (a > b ? (a = b) == b : false); } template<class S, class T> bool chmax(S &a, const T &b) { return (a < b ? (a = b) == b : false); } const ll inf = 1e18; const int mod = 1e9 + 7; struct Segment_Tree { int n; vector<ll> t, modify; Segment_Tree(int n) { this->n = n; t.assign(4 * n, -inf); modify.assign(4 * n, 0); } void push(int v, int tl, int tr) { t[v] += modify[v] * (tr - tl + 1); if (tl != tr) { modify[2 * v] += modify[v]; modify[2 * v + 1] += modify[v]; } modify[v] = 0; } void upd_pos(int v, int tl, int tr, int i, ll x) { if (tl == tr) { t[v] = x; return; } int tm = (tl + tr) >> 1; if (tm >= i) { upd_pos(2 * v, tl, tm, i, x); } else { upd_pos(2 * v + 1, tm + 1, tr, i, x); } t[v] = max(t[2 * v], t[2 * v + 1]); } void upd_pos(int i, ll x) { upd_pos(1, 0, n - 1, i, x); } void upd(int v, int tl, int tr, int l, int r, ll x) { if (modify[v]) { push(v, tl, tr); } if (tl > r || tr < l) { return; } if (tl >= l && tr <= r) { modify[v] += x; push(v, tl, tr); return; } int tm = (tl + tr) >> 1; upd(2 * v, tl, tm, l, r, x); upd(2 * v + 1, tm + 1, tr, l, r, x); t[v] = max(t[2 * v], t[2 * v + 1]); } void upd(int l, int r, ll x) { upd(1, 0, n - 1, l, r, x); } ll get(int v, int tl, int tr, int l, int r) { if (modify[v]) { push(v, tl, tr); } if (tl > r || tr < l) { return -inf; } if (tl >= l && tr <= r) { return t[v]; } int tm = (tl + tr) >> 1; return max(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r)); } int get(int i) { int lo = i, hi = n; while (lo + 1 < hi) { int mid = (lo + hi) >> 1; if (get(1, 0, n - 1, mid, n - 1) >= 0) { lo = mid; } else { hi = mid; } } return lo; } }; signed main() { cin.tie(nullptr)->sync_with_stdio(false); int n; cin >> n; ll x[n], g[n], d[n], pref[n]; for (int i = 0; i < n; ++i) { cin >> x[i] >> g[i] >> d[i]; } Segment_Tree t(n); ll sum = 0; for (int i = 0; i < n; ++i) { sum += d[i]; t.upd_pos(i, sum - x[i] + x[0]); pref[i] = (i == 0 ? 0 : pref[i - 1]) + g[i]; } auto gold = [&](int l, int r) { return pref[r] - (l == 0 ? 0 : pref[l - 1]); }; ll res = gold(0, t.get(0)); for (int i = 1; i < n; ++i) { t.upd(i, n - 1, x[i] - x[i - 1] - d[i - 1]); chmax(res, gold(i, t.get(i))); } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...