#include "candies.h"
#define here cerr<<"======================================\n"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll pair<ll,ll>
#define fi first
#define sc second
#define llinf 1000000000000000000LL
#define dbg(x) cerr<<#x<<": "<<x<<endl
using namespace std;
#define maxn 200005
ll n,q;
ll c[maxn];
vector<pll> v[maxn];
ll lazy[2*maxn];
ll ls[2*maxn],rs[2*maxn],root,tsz = 0;
struct nod{
ll mx,mn,mxid,mnid,val;
} t[2*maxn];
nod def,def0;
nod f(nod l,nod r){
nod ans;
ans.mn = min(l.mn,r.mn);
ans.mx = max(l.mx,r.mx);
if(l.mn<r.mn) ans.mnid = l.mnid;
else ans.mnid = r.mnid;
if(l.mx>r.mx) ans.mxid = l.mxid;
else ans.mxid = r.mxid;
ans.val = ans.mx-ans.mn;
return ans;
}
void init(ll &v,ll tl,ll tr){
if(!v) v = ++tsz;
t[v].mn = 0;
t[v].mx = 0;
t[v].mxid = tr;
t[v].mnid = tr;
t[v].val = 0;
if(tl==tr) return;
ll mid = (tl+tr)/2;
init(ls[v],tl,mid);
init(rs[v],mid+1,tr);
}
void push(ll v,ll tl,ll tr){
if(lazy[v]==0) return;
t[v].mn+=lazy[v];
t[v].mx+=lazy[v];
if(tl<tr){
lazy[ls[v]]+=lazy[v];
lazy[rs[v]]+=lazy[v];
}
lazy[v] = 0;
}
void upd(ll v,ll tl,ll tr,ll l,ll r,ll x){
push(v,tl,tr);
if(l>r||tl>tr||l>tr||tl>r) return;
if(tl>=l&&tr<=r){
lazy[v]+=x;
push(v,tl,tr);
return;
}
ll mid = (tl+tr)/2;
upd(ls[v],tl,mid,l,r,x);
upd(rs[v],mid+1,tr,l,r,x);
t[v] = f(t[ls[v]],t[rs[v]]);
}
ll get(ll v,ll tl,ll tr,ll x,nod cur){
push(v,tl,tr);
nod cur2 = f(t[v],cur);
if(cur2.val<x) return -1;
if(tl==tr) return tl;
ll mid = (tl+tr)/2;
push(ls[v],tl,tr);
push(rs[v],mid+1,tr);
ll ans = get(rs[v],mid+1,tr,x,cur);
if(ans==-1) return get(ls[v],tl,mid,x,f(t[rs[v]],cur));
return ans;
}
nod get(ll v,ll tl,ll tr,ll l,ll r){
push(v,tl,tr);
if(l>r||l>tr||tl>tr||tl>r) return def0;
if(tl>=l&&tr<=r) return t[v];
ll mid = (tl+tr)/2;
return f(get(ls[v],tl,mid,l,r),get(rs[v],mid+1,tr,l,r));
}
vector<int> ans;
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> VAL) {
n = C.size();
q = L.size();
for(ll i = 1;i<=n;i++) c[i] = C[i-1];
for(ll i = 1;i<=q;i++){
v[L[i-1]+1].pb({VAL[i-1],i+2});
v[R[i-1]+2].pb({-VAL[i-1],i+2});
}
q+=2;
init(root,1,q);
ll sum = 0;
nod def0;
def0.mn = llinf;
def0.mx = -llinf;
def0.mnid = def0.mxid = q+1;
def0.val = 0;
for(ll i = 1;i<=n;i++){
for(pll p : v[i]){
ll x = p.fi;
ll i = p.sc;
upd(root,1,q,i,q,x);
sum+=x;
}
push(1,1,q);
if(t[1].val<=c[i]){
if(t[1].mx>c[i]) ans.pb(c[i]+(sum-t[1].mx));
else{
ll j = t[1].mnid;
if(t[1].mn<0) ans.pb(sum-t[1].mn);
else ans.pb(sum);
}
continue;
}
nod def;
def.mn = llinf;
def.mx = -llinf;
def.mxid = q+1;
def.mnid = q+1;
def.val = 0;
ll j = get(1,1,q,c[i],def);
nod cur = get(1,1,q,j,q);
ll minid = cur.mnid;
ll maxid = cur.mxid;
if(minid>maxid) ans.pb(min(c[i],sum-cur.mn));
else ans.pb(max(0LL,c[i]+(sum-cur.mx)));
}
for(ll i = 0;i<n;i++) ans[i] = max(0LL,min(c[i+1],ans[i]));
return ans;
}
/**
3
10 15 13
2
0 2 20
0 1 -11
3
10 15 13
2
0 1 13
0 2 7
**/
Compilation message
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:116:20: warning: unused variable 'j' [-Wunused-variable]
116 | ll j = t[1].mnid;
| ^
candies.cpp:135:61: error: no matching function for call to 'min(long long int&, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&)'
135 | for(ll i = 0;i<n;i++) ans[i] = max(0LL,min(c[i+1],ans[i]));
| ^
In file included from /usr/include/c++/10/vector:60,
from candies.h:1,
from candies.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
candies.cpp:135:61: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
135 | for(ll i = 0;i<n;i++) ans[i] = max(0LL,min(c[i+1],ans[i]));
| ^
In file included from /usr/include/c++/10/vector:60,
from candies.h:1,
from candies.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
candies.cpp:135:61: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
135 | for(ll i = 0;i<n;i++) ans[i] = max(0LL,min(c[i+1],ans[i]));
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from candies.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3468 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
candies.cpp:135:61: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
135 | for(ll i = 0;i<n;i++) ans[i] = max(0LL,min(c[i+1],ans[i]));
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from candies.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3474 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: template argument deduction/substitution failed:
candies.cpp:135:61: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
135 | for(ll i = 0;i<n;i++) ans[i] = max(0LL,min(c[i+1],ans[i]));
| ^
