#include "candies.h" #include <vector> using namespace std; #define pb push_back using ll=long long; struct titem { ll sum, rmax, rmin; }; const int M = 262144; titem tree[M<<1]; void upd(int up, titem &&uv, int ti, int tl, int tr) { if (tl == tr) { tree[ti] = uv; return; } int md = (tl+tr)/2; if (up <= md) upd(up, move(uv), ti*2, tl, md); else upd(up, move(uv), ti*2+1, md+1, tr); tree[ti].sum = tree[ti*2].sum + tree[ti*2+1].sum; tree[ti].rmax = max(tree[ti*2].rmax + tree[ti*2+1].sum, tree[ti*2+1].rmax); tree[ti].rmin = min(tree[ti*2].rmin + tree[ti*2+1].sum, tree[ti*2+1].rmin); } vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) { int n = c.size(), q = l.size(); vector<vector<int>> events(n+1); for (int i=0; i<q; ++i) { events[l[i]].pb(i); events[r[i]+1].pb(i); } vector<int> ans(n); for (int i=0; i<n; ++i) { for (int qi: events[i]) { if (i == l[qi]) { upd(qi, titem{v[qi], max(0, v[qi]), min(0, v[qi])}, 1, 0, q-1); } else { upd(qi, titem{0, 0, 0}, 1, 0, q-1); } } int ti=1, tl=0, tr=q-1; ll brsum = 0, brmax = 0, brmin = 0; while (tl < tr) { int md = (tl+tr)/2; if (max(brsum + tree[ti*2+1].rmax, brmax)- min(brsum + tree[ti*2+1].rmin, brmin) <= c[i]) { brmax = max(brmax, brsum + tree[ti*2+1].rmax); brmin = min(brmin, brsum + tree[ti*2+1].rmin); brsum += tree[ti*2+1].sum; ti *= 2; tr = md; } else { ti = ti*2+1; tl = md+1; } } if (max(brsum + tree[ti].rmax, brmax) - min(brsum + tree[ti].rmin, brmin) <= c[i]) { ans[i] = tree[1].sum; } else { if (v[tl] > 0) { ans[i] = c[i] + brsum; } else { ans[i] = brsum; } } } return ans; }