#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll bucksize=450;
ll sol[200005];
ll cap[200005];
vector<ll> toprop[455];
ll n;
ll v[200005];
ll s[200005];
ll sufmin[200005],sufmax[200005];
ll getbuck(ll x)
{
return x/bucksize;
}
ll q;
vector<pll> ord;
void solve(ll poz)
{
sort(ord.begin(),ord.end());
if(poz+1<=q&&s[sufmin[poz+1]]-s[poz]<0)
poz=sufmin[poz+1];
while(!ord.empty())
{
if(poz==q)
{
for(auto i:ord)
sol[i.second]=0;
ord.clear();
break;
}
ll p=sufmax[poz+1];
ll val=s[p]-s[poz];
while(!ord.empty()&&ord.back().first>=val)
{
ll i=ord.back().second;
sol[i]=s[q]-s[poz];
ord.pop_back();
}
if(p==q)
{
for(auto i:ord)
sol[i.second]=i.first;
ord.clear();
break;
}
while(!ord.empty())
{
ll i=ord.back().second;
ll cc=ord.back().first;
ll x=s[sufmin[p+1]]-s[poz]-(val-cc);
if(x>=0)
{
sol[i]=s[q]-s[poz]-(val-cc);
ord.pop_back();
}
else
break;
}
poz=sufmin[p];
}
}
void solve2(ll p)
{
sort(ord.begin(),ord.end());
ll poz=0;
ll val=s[p]-s[poz];
if(p==q)
{
for(auto i:ord)
sol[i.second]=i.first;
ord.clear();
return;
}
while(!ord.empty())
{
ll i=ord.back().second;
ll cc=ord.back().first;
ll x=s[sufmin[p+1]]-s[poz]-(val-cc);
if(x>=0)
{
sol[i]=s[q]-s[poz]-(val-cc);
ord.pop_back();
}
else
break;
}
poz=sufmin[p];
while(!ord.empty())
{
if(poz==q)
{
for(auto i:ord)
sol[i.second]=0;
ord.clear();
break;
}
ll p=sufmax[poz+1];
ll val=s[p]-s[poz];
while(!ord.empty()&&ord.back().first>=val)
{
ll i=ord.back().second;
sol[i]=s[q]-s[poz];
ord.pop_back();
}
if(p==q)
{
for(auto i:ord)
sol[i.second]=i.first;
ord.clear();
break;
}
while(!ord.empty())
{
ll i=ord.back().second;
ll cc=ord.back().first;
ll x=s[sufmin[p+1]]-s[poz]-(val-cc);
if(x>=0)
{
sol[i]=s[q]-s[poz]-(val-cc);
ord.pop_back();
}
else
break;
}
poz=sufmin[p];
}
}
bool use[200005];
void prop(ll buck)
{
if(toprop[buck].empty())
return;
ll l=buck*bucksize;
ll r=min(n-1,l+bucksize-1);
for(int i=l;i<=r;i++)
use[i]=0;
q=toprop[buck].size();
for(int i=0;i<q;i++)
v[i+1]=toprop[buck][i];
toprop[buck].clear();
s[0]=0;
for(int i=1;i<=q;i++)
s[i]=s[i-1]+v[i];
sufmin[q]=q;
sufmax[q]=q;
for(int i=q-1;i>=1;i--)
{
sufmax[i]=sufmax[i+1];
sufmin[i]=sufmin[i+1];
if(s[i]>s[sufmax[i]])
sufmax[i]=i;
if(s[i]<s[sufmin[i]])
sufmin[i]=i;
}
ord.clear();
for(int i=l;i<=r;i++)
if(!use[i]&&sol[i]+s[sufmin[1]]<=0)
{
use[i]=1;
ord.push_back({cap[i],i});
}
solve(sufmin[1]);
ord.clear();
for(int i=l;i<=r;i++)
if(!use[i]&&sol[i]+s[sufmax[1]]<=cap[i])
{
use[i]=1;
sol[i]+=s[q];
}
for(int i=l;i<=r;i++)
if(!use[i])
{
use[i]=1;
ord.push_back({cap[i],i});
}
solve2(sufmax[1]);
}
void plsadd(ll l,ll r,ll val)
{
ll b1=getbuck(l);
ll b2=getbuck(r);
for(ll i=b1+1;i<b2;i++)
toprop[i].push_back(val);
prop(b1);
prop(b2);
for(ll i=l;i<=r&&getbuck(i)==b1;i++)
{
sol[i]+=val;
if(sol[i]<0)
sol[i]=0;
if(sol[i]>cap[i])
sol[i]=cap[i];
}
if(b1!=b2)
{
for(ll i=r;i>=l&&getbuck(i)==b2;i--)
{
sol[i]+=val;
if(sol[i]<0)
sol[i]=0;
if(sol[i]>cap[i])
sol[i]=cap[i];
}
}
}
ll mars[200005];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v)
{
n=c.size();
for(int i=0;i<c.size();i++)
cap[i]=c[i];
bool ok=1;
for(int i=0;i<v.size();i++)
if(v[i]<0)
ok=0;
if(ok)
{
for(ll i=0;i<l.size();i++)
{
ll st=l[i];
ll dr=r[i];
ll val=v[i];
mars[st]+=val;
mars[dr+1]-=val;
}
ll suma=0;
vector<int> ans;
for(ll i=0;i<n;i++)
{
suma+=v[i];
sol[i]=min(suma,cap[i]);
ans.push_back(sol[i]);
}
return ans;
}
for(int i=0;i<l.size();i++)
{
ll st=l[i];
ll dr=r[i];
ll val=v[i];
plsadd(st,dr,val);
}
for(ll b=0;bucksize*b<n;b++)
prop(b);
vector<int> ans;
for(int i=0;i<n;i++)
ans.push_back(sol[i]);
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:217:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
217 | for(int i=0;i<c.size();i++)
| ~^~~~~~~~~
candies.cpp:220:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
220 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
candies.cpp:225:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
225 | for(ll i=0;i<l.size();i++)
| ~^~~~~~~~~
candies.cpp:243:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
243 | for(int i=0;i<l.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
12152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
231 ms |
5136 KB |
Output is correct |
| 3 |
Correct |
57 ms |
8468 KB |
Output is correct |
| 4 |
Correct |
936 ms |
14164 KB |
Output is correct |
| 5 |
Correct |
1106 ms |
14184 KB |
Output is correct |
| 6 |
Correct |
4216 ms |
14316 KB |
Output is correct |
| 7 |
Correct |
4305 ms |
14216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
309 ms |
16284 KB |
Output is correct |
| 4 |
Correct |
60 ms |
13652 KB |
Output is correct |
| 5 |
Correct |
1750 ms |
720676 KB |
Output is correct |
| 6 |
Correct |
1780 ms |
720672 KB |
Output is correct |
| 7 |
Correct |
1721 ms |
720788 KB |
Output is correct |
| 8 |
Correct |
1763 ms |
720700 KB |
Output is correct |
| 9 |
Incorrect |
83 ms |
10580 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
