#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ll long long
ll masuf[1000000],misuf[1000000],sum[1000000];
ll a[1000000];
ll o=0;
void update(int v,int tl,int tr,int pos)
{
if(pos>tr||pos<tl)
return ;
if(tl==tr)
{
masuf[v]=max(o,a[pos]);
misuf[v]=min(o,a[pos]);
sum[v]=a[pos];
return ;
}
int tm=(tl+tr)/2;
update(v*2,tl,tm,pos);
update(v*2+1,tm+1,tr,pos);
sum[v]=sum[v*2]+sum[v*2+1];
misuf[v]=min(misuf[v*2+1],sum[v*2+1]+misuf[v*2]);
masuf[v]=max(masuf[v*2+1],sum[v*2+1]+masuf[v*2]);
}
ll get(int v,int tl,int tr,int l,int r)
{
if(l>r)
return 0;
if(tl==l&&tr==r)
{
return sum[v];
}
int tm=(tl+tr)/2;
if(r<=tm)
{
return get(v*2,tl,tm,l,r);
}
if(l>tm)
{
return get(v*2+1,tm+1,tr,l,r);
}
return get(v*2,tl,tm,l,tm)+get(v*2+1,tm+1,tr,tm+1,r);
}
pair<ll,pair<ll,ll> > getmin(int v,int tl,int tr,int l,int r)
{
if(tl==l&&tr==r)
{
return {sum[v],{misuf[v],tl}};
}
int tm=(tl+tr)/2;
if(r<=tm)
{
return getmin(v*2,tl,tm,l,r);
}
if(l>tm)
{
return getmin(v*2+1,tm+1,tr,l,r);
}
pair<ll,pair<ll,ll> >f=getmin(v*2,tl,tm,l,tm);
pair<ll,pair<ll,ll> >s=getmin(v*2+1,tm+1,tr,tm+1,r);
if(s.second.first<=s.first+f.second.first)
{
return{f.first+s.first,{min(s.second.first,s.first+f.second.first),s.second.second}};
}else
return {f.first+s.first,{min(s.second.first,s.first+f.second.first),f.second.second}};
}
pair<ll,pair<ll,ll > > getmax(int v,int tl,int tr,int l,int r)
{
if(tl==l&&tr==r)
{
return {sum[v],{masuf[v],tl}};
}
int tm=(tl+tr)/2;
if(r<=tm)
{
return getmax(v*2,tl,tm,l,r);
}
if(l>tm)
{
return getmax(v*2+1,tm+1,tr,l,r);
}
pair<ll,pair<ll,ll> >f=getmax(v*2,tl,tm,l,tm);
pair<ll,pair<ll,ll> >s=getmax(v*2+1,tm+1,tr,tm+1,r);
if(s.second.first>=s.first+f.second.first)
{
return{f.first+s.first,{max(s.second.first,s.first+f.second.first),s.second.second}};
}else
return {f.first+s.first,{max(s.second.first,s.first+f.second.first),f.second.second}};
}
vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v)
{
int n=c.size();
vector<int>ans;
vector<int>act[n+1];
int q=l.size();
for(int i=0;i<q;i++)
{
act[l[i]].push_back(i);
act[r[i]+1].push_back(i);
}
for(int i=0;i<n;i++)
{
for(auto y:act[i])
{
if(a[y]==0)
{
a[y]=v[y];
update(1,0,q-1,y);
}else
{
a[y]=0;
update(1,0,q-1,y);
}
}
int l=-1;
int r=q;
while(l+1<r)
{
int m=(l+r)/2;
ll mi=getmin(1,0,q-1,m,q-1).second.first;
ll ma=getmax(1,0,q-1,m,q-1).second.first;
// cout<<m<<' '<<mi<<' '<<ma<<endl;
if(abs(ma-mi)>=c[i])
{
l=m;
}else
r=m;
}
// cout<<r<<endl;
ll en=0;
if(l==-1||a[l]<0)
{
if(r==q)
{
ans.push_back(0);
continue;
}
en=getmax(1,0,q-1,r,q-1).second.second;
if(en==r&&getmax(1,0,q-1,r,q-1).second.first==get(1,0,q-1,r,q-1))
en--;
ans.push_back(get(1,0,q-1,en+1,q-1));
}
if(a[l]>0)
{
if(r==q)
{
ans.push_back(c[i]);
continue;
}
en=getmin(1,0,q-1,r,q-1).second.second;
// cout<<en<<' ';
if(en==r&&getmin(1,0,q-1,r,q-1).second.first==get(1,0,q-1,r,q-1))
en--;
// cout<<en<<' ';
// cout<<get(1,0,q-1,en+1,q-1)<<endl;
ans.push_back(c[i]+get(1,0,q-1,en+1,q-1));
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
0 ms |
312 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
671 ms |
36752 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
312 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Incorrect |
80 ms |
23372 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
0 ms |
312 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |