#include <bits/stdc++.h> using namespace std; #define ff first #define ss second const int N= 2e5+5; pair<int,int> mn[4*N],mx[4*N]; int lazy[4*N]; void applay(int node, int val) { mx[node].ff += val; mn[node].ff += val; lazy[node] += val; } void push(int node) { if (lazy[node] != 0) { applay(node*2,lazy[node]); applay(node*2+1,lazy[node]); lazy[node] = 0; } } void update(int node, int l, int r, int L, int R, int val) { if (l > R || r < L) return; if (l >= L && r <= R) { applay(node,val); return; } push(node); int 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 <int,int> getmax(int node, int l, int r, int L, int R) { if (l > R || r < L) return {-1e9,-1e9}; if (l >= L && r <= R) return mx[node]; push(node); int mid = (l+r)/2; return max(getmax(node*2,l,mid,L,R),getmax(node*2+1,mid+1,r,L,R)); } pair <int,int> getmin(int node, int l, int r, int L, int R) { if (l > R || r < L) return {1e9,1e9}; if (l >= L && r <= R) return mn[node]; push(node); int mid = (l+r)/2; return min(getmin(node*2,l,mid,L,R),getmin(node*2+1,mid+1,r,L,R)); } int get(int x,int q) { return getmax(1,0,q,x,x).ff; } void build(int node, int l, int r) { if (l == r) { mx[node] = {0,l}; mn[node] = {0,l}; return; } int mid = (l+r)/2; build(node*2,l,mid); build(node*2+1,mid+1,r); } 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(i+1,v[i]); if (r[i] != n-1) res[r[i]+1].emplace_back(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); } int 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; }