# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
807731 | Mouad_ouj | Distributing Candies (IOI21_candies) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
int tree[40000]={0},lazy[40000]={0};
void upd(int p,int l,int r,int a,int b,int n)
{
if(lazy[p]!=0)
{
tree[p]+=(r-l+1)*lazy[p];
if(l!=r)
{
lazy[2*p+1]+=lazy[p];
lazy[2*p+2]+=lazy[p];
}
lazy[p]=0;
}
if(l>b || r<a)
return;
if(l>=a && r<=b)
{
tree[p]+=n*(r-l+1);
if(l!=r)
{
lazy[2*p+1]+=n;
lazy[2*p+2]+=n;
}
return;
}
int mid=(l+r)/2;
upd(2*p+1,l,mid,a,b,n);
upd(2*p+2,mid+1,r,a,b,n);
tree[p]=tree[2*p+1]+tree[2*p+2];
}
int get(int p,int l,int r,int cur)
{
if(cur>r || cur<l)
return 0;
if(lazy[p]!=0)
{
tree[p]+=(r-l+1)*lazy[p];
if(l!=r)
{
lazy[2*p+1]+=lazy[p];
lazy[2*p+2]+=lazy[p];
}
lazy[p]=0;
}
if(cur==l && cur==r)
return tree[p];
int mid=(l+r)/2;
return get(2*p+1,l,mid,cur)+get(2*p+2,mid+1,r,cur);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
vector<int> a;
a.assign(c.size(),0);
for(int y=0;y<l.size();y++)
upd(0,l[y],r[y],v[y]);
for(int x=0;x<c.size();x++)
a[x]=min(get(0,0,n-1,x),c[x]);
return a;
}