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 <bits/stdc++.h>
#include <vector>
using namespace std;
const int MAXN = 2e6+2;
int c[MAXN];
vector <int> ans;
struct Segment
{
int minel[MAXN],maxel[MAXN], lazy[MAXN];
void update_lazy(int v, int from, int to)
{
if(lazy[v]==0)return ;
minel[2*v]+=lazy[v];
maxel[2*v]+=lazy[v];
minel[2*v+1]+=lazy[v];
maxel[2*v+1]+=lazy[v];
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[v] = 0;
}
void update(int v,int from, int to, int l, int r, int delta)
{
// cout<<"UPDATE:: "<<v<<" "<<from<<" "<<to<<" "<<l<<" "<<r<<" "<<delta<<endl;
if(from==to)
{
minel[v] = max(0, min(c[from],minel[v]+delta));
maxel[v] = max(0, min(c[from],maxel[v]+delta));
// cout<<v<<" "<<minel[v]<<" "<<maxel[v]<<endl;
return ;
}
update_lazy(v,from,to);
int mid = (from+to)/2;
if(l<=from&&to<=r)
{
minel[v]+=delta;
maxel[v]+=delta;
if(minel[v]<0||maxel[v]>c[0])
{
update(2*v,from,mid,l,r,delta);
update(2*v+1,mid+1,to,l,r,delta);
minel[v] = min(minel[2*v],minel[2*v+1]);
maxel[v] = max(maxel[2*v],maxel[2*v+1]);
}
else
lazy[v]+=delta;
return ;
}
if(l<=mid)
update(2*v,from,mid,l,r,delta);
if(r>mid)
update(2*v+1,mid+1,to,l,r,delta);
minel[v] = min(minel[2*v],minel[2*v+1]);
maxel[v] = max(maxel[2*v],maxel[2*v+1]);
// cout<<v<<" "<<minel[v]<<" "<<maxel[v]<<endl;
}
void query(int v, int from, int to)
{
if(from==to)
{
// cout<<"-> "<<from<<" "<<minel[v]<<endl;
ans[from] = minel[v];
return ;
}
int mid = (from+to)/2;
update_lazy(v,from,to);
query(2*v,from,mid);
query(2*v+1,mid+1,to);
}
};
Segment S;
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 i,j;
for(i = 0; i<n;i++)
c[i] = _c[i];
for(i=0;i<l.size();i++)
{
S.update(1,0,n-1,l[i],r[i],v[i]);
}
ans.resize(n);
S.query(1,0,n-1);
return ans;
}
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:77:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(i=0;i<l.size();i++)
| ~^~~~~~~~~
candies.cpp:74:11: warning: unused variable 'j' [-Wunused-variable]
74 | int i,j;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |