This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "candies.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int llint;
llint off=1,t[500005],t1[500005],p[500005],n,q;
void send(int x) {
if(!p[x]) return;
t[x]=max(0LL,t[x]-p[x]);
if(x<off) {
p[x*2]+=p[x];
p[x*2+1]+=p[x];
}
p[x]=0;
}
void update(int x,int lo,int hi,int l,int r,llint v1) {
send(x);
if(lo>r || hi<l) return;
if(lo>=l && hi<=r) {
p[x]+=v1;
send(x);
return;
}
update(x*2,lo,(lo+hi)/2,l,r,v1);
update(x*2+1,(lo+hi)/2+1,hi,l,r,v1);
t[x]=max(t[x*2],t[x*2+1]);
}
llint query(int x,int lo,int hi,int l,int r) {
send(x);
if(lo>r || hi<l) return 0;
if(lo>=l && hi<=r) return t[x];
return max(query(x*2,lo,(lo+hi)/2,l,r),query(x*2+1,(lo+hi)/2+1,hi,l,r));
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v) {
n=c.size();
q=l.size();
vector<int> s(n);
while(off<n) off*=2;
int mini=1e9;
for(int i=0;i<q;i++) mini=min(mini,v[i]);
if(mini>0) {
for(int i=0;i<n;i++) {
update(1,0,off-1,i,i,-c[i]);
}
for(int i=0;i<q;i++) {
update(1,0,off-1,l[i],r[i],v[i]);
}
for(int i=0;i<n;i++) {
s[i]=c[i]-query(1,0,off-1,i,i);
}
}
else if(n<=2000) {
for(int i=0;i<n;i++) {
s[i]=0;
}
for(int i=0;i<q;i++) {
if(v[i]<0) {
for(int j=l[i];j<=r[i];j++) {
s[j]=max(0LL,s[j]+v[i]);
}
}
else{
for(int j=l[i];j<=r[i];j++) {
s[j]=min(c[j],s[j]+v[i]);
}
}
}
}
return s;
}
Compilation message (stderr)
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:60:28: error: no matching function for call to 'max(long long int, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type)'
60 | s[j]=max(0LL,s[j]+v[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:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
candies.cpp:60:28: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
60 | s[j]=max(0LL,s[j]+v[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:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
candies.cpp:60:28: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
60 | s[j]=max(0LL,s[j]+v[i]);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from candies.cpp:4:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
candies.cpp:60:28: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
60 | s[j]=max(0LL,s[j]+v[i]);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from candies.cpp:4:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
candies.cpp:60:28: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
60 | s[j]=max(0LL,s[j]+v[i]);
| ^