#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];
}
}
}
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];
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:219:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
219 | for(int i=0;i<c.size();i++)
| ~^~~~~~~~~
candies.cpp:221:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
221 | for(int i=0;i<l.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
20 ms |
408 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5072 ms |
16232 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
235 ms |
8132 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
326 ms |
18848 KB |
Output is correct |
| 4 |
Correct |
64 ms |
14788 KB |
Output is correct |
| 5 |
Correct |
1926 ms |
724160 KB |
Output is correct |
| 6 |
Correct |
1872 ms |
724756 KB |
Output is correct |
| 7 |
Correct |
1841 ms |
725440 KB |
Output is correct |
| 8 |
Correct |
1825 ms |
724104 KB |
Output is correct |
| 9 |
Correct |
1680 ms |
725528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
20 ms |
408 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
