#include<bits/stdc++.h>
using namespace std;
#include "candies.h"
//#include "grader.cpp"
#define pb push_back
#define X first
#define Y second
int mx[800005],mn[800005],lz[800005];
vector<pair<int,int> > sweep[200005]; // pair (index of commands, updated value)
vector<int> ans;
void uptlz(int tree,int st,int 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(int tree,int st,int ed,int l,int r,int val)
{
int 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]);
}
pair<int,int> query(int tree,int st,int ed,int l,int r)
{
int md=(st+ed)/2;
uptlz(tree,st,ed);
if(st>r||ed<l)return {-1e9,1e9};
if(st>=l&&ed<=r)return {mx[tree],mn[tree]};
return {max(query(2*tree,st,md,l,r).X,query(2*tree+1,md+1,ed,l,r).X),min(query(2*tree,st,md,l,r).Y,query(2*tree+1,md+1,ed,l,r).Y)};
}
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(),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("%d ",query(1,1,m,j,j));
}
printf("\n");*/
int st=0,md,ed=m;
while(ed>=st)
{
md=(st+ed)/2;
int diff;
if(md==0)
{
diff=query(1,1,m,1,m).X;
}else
{
diff=query(1,1,m,md,m).X-query(1,1,m,md,m).Y;
}
if(diff>c[i-1])
{
st=md+1;
}else
{
ed=md-1;
}
}
int fn=query(1,1,m,m,m).X;//final point
int l1,r1,l2,r2,base;
if(ed==-1)
{
ans.pb(max(fn,0));
}else
{
if(ed==0)
{
l1=0;
r1=query(1,1,m,1,m).X;
}else
{
l1=query(1,1,m,ed,m).Y;
r1=query(1,1,m,ed,m).X;
}
l2=query(1,1,m,ed+1,m).Y;
r2=query(1,1,m,ed+1,m).X;
if(l1==l2)
{
base=l1;
}else
{
base=r1-c[i-1];
}
ans.pb(fn-base);
}
}
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:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int j=0;j<sweep[i].size();j++)
| ~^~~~~~~~~~~~~~~~
candies.cpp:94:22: warning: variable 'r2' set but not used [-Wunused-but-set-variable]
94 | int 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 |
Execution timed out |
5071 ms |
21316 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4948 KB |
Output is correct |
| 3 |
Execution timed out |
5083 ms |
19120 KB |
Time limit exceeded |
| 4 |
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 |
- |
