#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>
#include <climits>
using namespace std;
#define ll long long
const ll inf=1e18;
const ll N=2e5+3;
int qp;
vector<pair<int,int>> T[N];
struct Data
{
ll sum=0;
ll mi=0;
ll mx=0;
ll lazy=0;
};
Data idendity{0,inf,-inf,0};
Data join(Data l,Data r)
{
return Data{l.sum+r.sum,min(l.mi,r.mi),max(l.mx,r.mx),0};
}
struct SegmentTree
{
Data val;
int s,e;
SegmentTree* next[2];
SegmentTree(int l,int r)
{
s=l;
e=r;
if(s!=e)
{
int mid=(s+e)/2;
next[0]=new SegmentTree(s,mid);
next[1]=new SegmentTree(mid+1,e);
}
}
void push()
{
val.sum+=(e-s+1)*val.lazy;
val.mi+=val.lazy;
val.mx+=val.lazy;
if(s!=e)
{
next[0]->val.lazy+=val.lazy;
next[1]->val.lazy+=val.lazy;
}
val.lazy=0;
}
void pull()
{
val=join(next[0]->val,next[1]->val);
}
void Update(int l,int r,ll v)
{
push();
if(r<s or e<l)
return;
if(l<=s and e<=r)
{
val.lazy+=v;
push();
return;
}
next[0]->Update(l,r,v);
next[1]->Update(l,r,v);
pull();
}
int Just(ll al,ll mx=-inf,ll mi=inf) // al == ci , [s, e] -> s
{
if(s==e)
{
return s;
}
else
{
next[1]->push();
next[0]->push();
ll nmx=max(mx,next[1]->val.mx);
ll nmi=min(mi,next[1]->val.mi);
if((nmx-nmi)>=al)
{
// answer is in the range
return next[1]->Just(al, nmx, nmi);
}
else
{
return next[0]->Just(al,nmx,nmi);
}
}
}
Data get(int l,int r=qp)
{
push();
if(r<s or e<l)
return idendity;
if(l<=s and e<=r)
return val;
return join(next[0]->get(l),next[1]->get(l));
}
};
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();
int q=l.size();
qp=q;
SegmentTree* st=new SegmentTree(0,qp);
for(int i=0;i<q;i++)
{
T[l[i]].push_back({v[i],i+1});
T[r[i]+1].push_back({-v[i],i+1});
}
vector<int> ans(n);
ll tpot=0;
for(int j=0;j<n;j++)
{
for(auto fi:T[j])
{
tpot+=fi.first;
st->Update(fi.second,qp,fi.first);
}
long long cp=c[j];
Data curap=st->get(0);
if((curap.mx-curap.mi)<=cp)
{
ans[j]=(tpot-curap.mi);
continue;
}
int s=st->Just(cp);
curap=st->get(s);
auto lpa=curap;
curap=st->get(s+1) ;
if(lpa.mx==curap.mx)
ans[j]=tpot-lpa.mx+cp;
else
ans[j]=tpot-lpa.mi;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
485 ms |
44264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
