#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;
ll minin[1000000],maxin[1000000];
void update(int v,int tl,int tr,int pos)
{
if(pos>tr||pos<tl)
return ;
if(tl==tr)
{
masuf[v]=a[pos];
misuf[v]=a[pos];
sum[v]=a[pos];
maxin[v]=tl;
minin[v]=tl;
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];
if(misuf[v*2+1]<=sum[v*2+1]+misuf[v*2])
{
minin[v]=minin[v*2+1];
}else
minin[v]=minin[v*2];
if(masuf[v*2+1]>=sum[v*2+1]+masuf[v*2])
{
maxin[v]=maxin[v*2+1];
}else
maxin[v]=maxin[v*2];
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],minin[v]}};
}
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],maxin[v]}};
}
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=min(o,getmin(1,0,q-1,m,q-1).second.first);
ll ma=max(o,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(getmax(1,0,q-1,r,q-1).second.first<o)
{
ans.push_back(0);
continue;
}
// en--;
ans.push_back(get(1,0,q-1,en,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<<' '<<getmin(1,0,q-1,r,q-1).second.first<<' '<<get(1,0,q-1,r,q-1)<<' ';
if(getmin(1,0,q-1,r,q-1).second.first>o)
{
ans.push_back(c[i]);
continue;
}
// cout<<en<<' ';
// cout<<get(1,0,q-1,en,q-1)<<endl;
ans.push_back(c[i]+get(1,0,q-1,en,q-1));
}
}
return ans;
}
| # |
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 |
Execution timed out |
5035 ms |
103592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
304 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 |
- |
