#include <bits/stdc++.h> #define pb push_back #define fst first #define snd second #define fore(i,a,b) for(int i=a,pao=b;i<pao;++i) #define SZ(x) ((int)x.size()) #define ALL(x) x.begin(),x.end() #define mset(a,v) memset((a),(v),sizeof(a)) #define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) using namespace std; typedef long long ll; const int MAXN=2e5+9; const ll INF=1e18; struct Nodo{ ll mn=0,mx=0,lz=0; }; Nodo st[MAXN*4]; int n,q; void appl(int v,ll x){ st[v].mn+=x; st[v].mx+=x; st[v].lz+=x; } void push(int v){ appl(v*2,st[v].lz); appl(v*2+1,st[v].lz); st[v].lz=0; } void upd(int ts,int te,int x,int v=1,int s=0,int e=q){ if(e<ts||te<s)return; if(ts<=s&&e<=te){ appl(v,x); return; }else{ push(v); int m=(s+e)/2; upd(ts,te,x,v*2,s,m); upd(ts,te,x,v*2+1,m+1,e); st[v].mn=min(st[v*2].mn,st[v*2+1].mn); st[v].mx=max(st[v*2].mx,st[v*2+1].mx); } } pair<ll,ll> que(int ts,int te,int v=1,int s=0,int e=q){ if(e<ts||te<s)return make_pair(INF,-INF); if(ts<=s&&e<=te){ return make_pair(st[v].mn,st[v].mx); }else{ push(v); int m=(s+e)/2; auto a=que(ts,te,v*2,s,m); auto b=que(ts,te,v*2+1,m+1,e); return make_pair(min(a.fst,b.fst),max(a.snd,b.snd)); } } std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) { n=SZ(c),q=SZ(l); vector<vector<pair<int,int>>>ty(n); fore(i,0,q){ ty[l[i]].emplace_back(i+1,v[i]); if(r[i]+1<n)ty[r[i]+1].emplace_back(i+1,-v[i]); } vector<int>ret(n); fore(i,0,n){ fore(j,0,SZ(ty[i])){ upd(ty[i][j].fst,q,ty[i][j].snd); } ll sum=que(q,q).snd; if(st[1].mx-st[1].mn<=c[i]){ ret[i]=sum-st[1].mn; } int L=0,R=q+1; while(R-L>1){ int m=(L+R)/2; auto a=que(m,q); if(a.snd-a.fst>=c[i]){ L=m; }else R=m; } if(que(0,L).snd<=sum){ ret[i]=c[i]-(que(L,q).snd-sum); }else{ ret[i]=sum-que(L,q).fst; } } return ret; }