#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
const ll INF=1e9;
ll m;
struct node
{
int max1;
int max2;
bool nomax2,nomin2;
int min1;
int min2;
int toAdd;
int maxx()
{
int ret=max1;
if(!nomax2)ret=max(ret,max2);
ret=max(ret,min1);
if(!nomin2)
{
ret=max(ret,min2);
}
return ret;
}
};
int t=0;
node tree[4*MAXN];
node merge(node n1,node n2)
{
node ret;
set<int>maxes;
maxes.insert(n1.max1+n1.toAdd);
maxes.insert(n1.max2+n1.toAdd);
maxes.insert(n2.max1+n2.toAdd);
maxes.insert(n2.max2+n2.toAdd);
set<int>mins;
mins.insert(n1.min1+n1.toAdd);
mins.insert(n1.min2+n1.toAdd);
mins.insert(n2.min1+n2.toAdd);
mins.insert(n2.min2+n2.toAdd);
ret.toAdd=0;
ret.min1=(*mins.begin());
mins.erase(mins.begin());
if(mins.size()>0)ret.min2=(*mins.begin());
else {ret.min2=+INF;ret.nomin2=1;}
ret.max1=(*maxes.rbegin());
maxes.erase((*maxes.rbegin()));
if(maxes.size()>0)ret.max2=(*maxes.rbegin());
else {ret.max2=-INF;ret.nomax2=1;}
return ret;
}
void build(int l,int r,int idx)
{
if(l==r)
{
tree[idx].max1=tree[idx].min1=0;
tree[idx].max2=0;
tree[idx].min2=m;
tree[idx].nomax2=1;
tree[idx].nomin2=1;
tree[idx].toAdd=0;
return;
}
int mid=(l+r)/2;
build(l,mid,idx*2);
build(mid+1,r,idx*2+1);
tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
}
void push(int l,int r,int idx)
{
tree[idx].max1+=tree[idx].toAdd;
tree[idx].max2+=tree[idx].toAdd;
tree[idx].min1+=tree[idx].toAdd;
tree[idx].min2+=tree[idx].toAdd;
if(l!=r)
{
tree[idx*2].toAdd+=tree[idx].toAdd;
tree[idx*2+1].toAdd+=tree[idx].toAdd;
tree[idx*2].max1=min(tree[idx*2].max1,tree[idx].max1-tree[idx*2].toAdd);
tree[idx*2+1].max1=min(tree[idx*2+1].max1,tree[idx].max1-tree[idx*2+1].toAdd);
tree[idx*2].min1=max(tree[idx*2].min1,tree[idx].min1-tree[idx*2].toAdd);
tree[idx*2+1].min1=max(tree[idx*2+1].min1,tree[idx].min1-tree[idx*2+1].toAdd);
}
tree[idx].toAdd=0;
}
void minWithSafe(int l,int r,int idx,int val)
{
tree[idx].max1=min(tree[idx].max1,val-tree[idx].toAdd);
push(l,r,idx);
}
void maxWithSafe(int l,int r,int idx,int val)
{
tree[idx].min1=max(tree[idx].min1,val-tree[idx].toAdd);
push(l,r,idx);
}
void minWith(int l,int r,int idx,int ql,int qr,int val)
{
push(l,r,idx);
if(l>qr)return;
if(r<ql)return;
if(tree[idx].max1<=val)return;
if(l>=ql&&r<=qr&&tree[idx].max2<val)
{
minWithSafe(l,r,idx,val);
return;
}
int mid=(l+r)/2;
minWith(l,mid,idx*2,ql,qr,val);
minWith(mid+1,r,idx*2+1,ql,qr,val);
tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
}
void maxWith(int l,int r,int idx,int ql,int qr,int val)
{
push(l,r,idx);
if(l>qr)return;
if(r<ql)return;
if(tree[idx].min1>=val)return;
if(l>=ql&&r<=qr&&tree[idx].min2>val)
{
maxWithSafe(l,r,idx,val);
return;
}
int mid=(l+r)/2;
maxWith(l,mid,idx*2,ql,qr,val);
maxWith(mid+1,r,idx*2+1,ql,qr,val);
tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
}
void update(int l,int r,int idx,int ql,int qr,int val)
{
push(l,r,idx);
if(l>qr)return;
if(r<ql)return;
if(l>=ql&&r<=qr)
{
tree[idx].toAdd+=val;
push(l,r,idx);
return;
}
int mid=(l+r)/2;
update(l,mid,idx*2,ql,qr,val);
update(mid+1,r,idx*2+1,ql,qr,val);
tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
}
int query(int l,int r,int idx,int ql,int qr)
{
push(l,r,idx);
if(l>qr)return -INF;
if(r<ql)return -INF;
if(l>=ql&&r<=qr)return tree[idx].maxx();
int mid=(l+r)/2;
return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
ll n = c.size(),q=l.size();m=c[0];
vector<int>s(n,0);
build(1,n,1);
for(int i=0;i<q;i++)
{
l[i]++;r[i]++;
update(1,n,1,l[i],r[i],v[i]);
//cout<<i<<" - 1\n";
//for(int j=0;j<n;j++)cout<<query(1,n,1,j+1,j+1)<<" ";
//cout<<endl;
//cout<<i<<" - 2\n";
minWith(1,n,1,1,n,c[0]);
//for(int j=0;j<n;j++)cout<<query(1,n,1,j+1,j+1)<<" ";
//cout<<endl;
//cout<<i<<" - 3\n";
maxWith(1,n,1,1,n,0);
//for(int j=0;j<n;j++)cout<<query(1,n,1,j+1,j+1)<<" ";
//cout<<endl;
}
for(int i=0;i<n;i++)
{
s[i]=query(1,n,1,i+1,i+1);
}
return s;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
157 ms |
39620 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
