#include <bits/stdc++.h> using namespace std; #define ff first #define ss second const int N= 2e5+5; pair<long long,long long> mn[4*N],mx[4*N]; long long lazy[4*N]; void applay(long long node, long long val) { mx[node].ff += val; mn[node].ff += val; lazy[node] += val; } void push(long long node) { if (lazy[node] != 0) { applay(node*2,lazy[node]); applay(node*2+1,lazy[node]); lazy[node] = 0; } } void update(long long node, long long l, long long r, long long L, long long R, long long val) { if (l > R || r < L) return; if (l >= L && r <= R) { applay(node,val); return; } push(node); long long mid = (l+r)/2; update(node*2,l,mid,L,R,val); update(node*2+1,mid+1,r,L,R,val); mn[node] = min(mn[node*2],mn[node*2+1]); mx[node] = max(mx[node*2],mx[node*2+1]); } pair <long long,long long> getmax(long long node, long long l, long long r, long long L, long long R) { if (l > R || r < L) return {-2e18,-2e18}; if (l >= L && r <= R) return mx[node]; push(node); long long mid = (l+r)/2; return max(getmax(node*2,l,mid,L,R),getmax(node*2+1,mid+1,r,L,R)); } pair <long long,long long> getmin(long long node, long long l, long long r, long long L, long long R) { if (l > R || r < L) return {2e18,2e18}; if (l >= L && r <= R) return mn[node]; push(node); long long mid = (l+r)/2; return min(getmin(node*2,l,mid,L,R),getmin(node*2+1,mid+1,r,L,R)); } long long get(long long x,long long q) { return getmax(1,0,q,x,x).ff; } void build(long long node, long long l, long long r) { if (l == r) { mx[node] = {0,l}; mn[node] = {0,l}; return; } long long mid = (l+r)/2; build(node*2,l,mid); build(node*2+1,mid+1,r); mn[node] = min(mn[node*2],mn[node*2+1]); mx[node] = max(mx[node*2],mx[node*2+1]); } std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) { int n = c.size(); int q = l.size(); vector <vector<pair<int,int>>> res(n+5); build(1,0,q); for (int i = 0; i < q; i++) { res[l[i]].emplace_back(make_pair(i+1,v[i])); res[r[i]+1].emplace_back(make_pair(i+1,-v[i])); } vector <int> s(n); for (int i = 0; i < n; i++) { for (auto [pos,val]:res[i]) { update(1,0,q,pos,q,val); } long long sum = get(q,q); if (mx[1].ff-mn[1].ff <= c[i]) { s[i] = sum-mn[1].ff; continue; } int l = 1; int r = q; int ans = -1; while (l <= r) { int mid = (l+r)/2; if (getmax(1,0,q,mid,q).ff-getmin(1,0,q,mid,q).ff >= c[i]) { ans = mid; l = mid + 1; } else { r = mid -1; } } auto mx1 = getmax(1,0,q,ans,q); auto mn1 = getmin(1,0,q,ans,q); if (mx1.ss <= mn1.ss) { s[i] = sum-mn1.ff; } else { s[i] = c[i]+(sum-mx1.ff); } } return s; }