#include<bits/stdc++.h>
using namespace std;
#include "candies.h"
//#include "grader.cpp"
#define pb push_back
#define X first
#define Y second
#define ll long long
ll mx[800005],mn[800005],lz[800005];
vector<pair<ll,ll> > sweep[200005]; // pair (index of commands, updated value)
vector<int> ans;
void uptlz(ll tree,ll st,ll ed)
{
mx[tree]+=lz[tree],mn[tree]+=lz[tree];
if(st!=ed)
{
lz[2*tree]+=lz[tree],lz[2*tree+1]+=lz[tree];
}
lz[tree]=0;
}
void update(ll tree,ll st,ll ed,ll l,ll r,ll val)
{
ll md=(st+ed)/2;
if(st>=l&&ed<=r)
{
lz[tree]+=val;
}
uptlz(tree,st,ed);
if(st>r||ed<l)return;
if(st>=l&&ed<=r)return;
update(2*tree,st,md,l,r,val);
update(2*tree+1,md+1,ed,l,r,val);
mx[tree]=max(mx[2*tree],mx[2*tree+1]);
mn[tree]=min(mn[2*tree],mn[2*tree+1]);
}
ll query_mx(ll tree,ll st,ll ed,ll l,ll r)
{
ll md=(st+ed)/2;
uptlz(tree,st,ed);
if(st>r||ed<l)return -1e18;
if(st>=l&&ed<=r)return mx[tree];
return max(query_mx(2*tree,st,md,l,r),query_mx(2*tree+1,md+1,ed,l,r));
}
ll query_mn(ll tree,ll st,ll ed,ll l,ll r)
{
ll md=(st+ed)/2;
uptlz(tree,st,ed);
if(st>r||ed<l)return 1e18;
if(st>=l&&ed<=r)return mn[tree];
return min(query_mn(2*tree,st,md,l,r),query_mn(2*tree+1,md+1,ed,l,r));
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
ll n = c.size();
ll m=v.size();
for(int i=0;i<m;i++)
{
sweep[l[i]+1].pb({i+1,v[i]});
sweep[r[i]+2].pb({i+1,-v[i]});
}
/*for(int i=1;i<=n;i++)
{
printf("%d\n",i);
for(int j=0;j<sweep[i].size();j++)
{
printf("%d %d\n",sweep[i][j].X,sweep[i][j].Y);
}
printf("\n");
}*/
for(int i=1;i<=n;i++)
{
for(int j=0;j<sweep[i].size();j++)
{
int cmd=sweep[i][j].X,flag=sweep[i][j].Y;
update(1,1,m,cmd,m,flag);
}
/*printf("i=%d\n",i);
for(int j=1;j<=m;j++)
{
printf("%lld ",query(1,1,m,j,j));
}
printf("\n");*/
ll st=0,md,ed=m;
while(ed>=st)
{
md=(st+ed)/2;
ll diff;
pair<ll,ll> rng={query_mx(1,1,m,md,m),query_mn(1,1,m,md,m)};
if(md==0)
{
diff=query_mx(1,1,m,1,m);
}else
{
diff=rng.X-rng.Y;
}
if(diff>c[i-1])
{
st=md+1;
}else
{
ed=md-1;
}
}
ll fn=query_mx(1,1,m,m,m);//final poll
ll l1,r1,l2,r2,base;
if(ed==-1)
{
l1=min((ll)0,query_mn(1,1,m,1,m));
r1=query_mx(1,1,m,1,m);
ans.pb(fn-l1);
}else
{
if(ed==0)
{
l1=0;
r1=query_mx(1,1,m,1,m);
}else
{
l1=query_mn(1,1,m,ed,m);
r1=query_mx(1,1,m,ed,m);
}
l2=query_mn(1,1,m,ed+1,m);
r2=query_mx(1,1,m,ed+1,m);
if(l1==l2)
{
base=l1;
}else
{
base=r1-c[i-1];
}
ans.pb(fn-base);
}
ans.pb(0);
}
return ans;
}
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:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int j=0;j<sweep[i].size();j++)
| ~^~~~~~~~~~~~~~~~
candies.cpp:105:21: warning: variable 'r2' set but not used [-Wunused-but-set-variable]
105 | ll l1,r1,l2,r2,base;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1890 ms |
37596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
