Submission #523240

#TimeUsernameProblemLanguageResultExecution timeMemory
523240boykutDivide and conquer (IZhO14_divide)C++14
100 / 100
206 ms149828 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const long long INF = 1e18, Lim = 1e14; struct segment_tree { long long v, vl, vr; segment_tree * left, * right; segment_tree(long long l, long long r) { vl = l, vr = r; v = INF; left = right = NULL; } void update(long long i, long long x) { if (vl == vr) { v = min(v, x); } else { long long vm = vl + (vr - vl) / 2; if (i <= vm) { if (left == NULL) left = new segment_tree(vl, vm); left->update(i, x); } else { if (right == NULL) right = new segment_tree(vm + 1, vr); right->update(i, x); } v = min((left != NULL ? left->v : INF), (right != NULL ? right->v : INF)); } } long long query(long long l, long long r) { if (l > vr || vl > r) return INF; if (l <= vl && vr <= r) return v; long long vm = vl + (vr - vl) / 2; auto L = (left != NULL ? left->query(l, r) : INF); auto R = (right != NULL ? right->query(l, r) : INF); return min(L, R); } }; int main() { ios::sync_with_stdio(0); cin.tie(0); segment_tree st(-Lim, Lim); int n; cin >> n; vector<int> x(1 + n), g(1 + n), d(1 + n); for (int i = 1; i <= n; i++) { cin >> x[i] >> g[i] >> d[i]; } vector<long long> pd(1 + n, 0), pg(1 + n, 0), PG(1 + n, 0); for (int i = 1; i <= n; i++) { pd[i] = d[i] + pd[i - 1]; pg[i] = g[i] + pg[i - 1]; } long long ans = 0; for (int r = 1; r <= n; r++) { st.update(pd[r - 1] - x[r], pg[r - 1]); ans = max(ans, pg[r] - st.query(-Lim, pd[r] - x[r])); } cout << ans << '\n'; return 0; }

Compilation message (stderr)

divide.cpp: In member function 'long long int segment_tree::query(long long int, long long int)':
divide.cpp:39:13: warning: unused variable 'vm' [-Wunused-variable]
   39 |   long long vm = vl + (vr - vl) / 2;
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...