#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'
#include "candies.h"
#include <vector>
llo tree[4*200001][4];
llo lazy[4*200001];
//min
//max
//max-min
vector<pair<int,int>> pre[200001];
vector<pair<int,int>> pre2[200001];
llo vis[200001];
void push(int no,int l,int r){
tree[no][0]+=lazy[no];
tree[no][1]+=lazy[no];
if(l<r){
lazy[no*2+1]+=lazy[no];
lazy[no*2+2]+=lazy[no];
}
lazy[no]=0;
}
void update(int no,int l,int r,int aa,int bb,int x){
push(no,l,r);
if(l>bb or r<aa or aa>bb){
return;
}
if(aa<=l and r<=bb){
lazy[no]+=x;
push(no,l,r);
}
else{
int mid=(l+r)/2;
update(no*2+1,l,mid,aa,bb,x);
update(no*2+2,mid+1,r,aa,bb,x);
tree[no][0]=min(tree[no*2+1][0],tree[no*2+2][0]);
tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]);
tree[no][2]=min(tree[no*2+1][2],tree[no*2+2][2]);
tree[no][2]=min(tree[no][2],tree[no*2+2][0]-tree[no*2+1][1]);
tree[no][3]=max(tree[no*2+1][3],tree[no*2+2][3]);
tree[no][3]=max(tree[no][3],tree[no*2+2][1]-tree[no*2+1][0]);
}
}
llo query(int no,int l,int r,int aa,int bb){
push(no,l,r);
if(r<aa or l>bb or aa>bb){
return (llo)1e18;
}
if(aa<=l and r<=bb){
return tree[no][0];
}
int mid=(l+r)/2;
return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
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();
vector<int> ans;
int q=l.size();
for(int i=0;i<q;i++){
pre[l[i]].pb({i,v[i]});
}
for(int i=0;i<q;i++){
pre2[r[i]].pb({i,v[i]});
}
llo su=0;
for(int i=0;i<n;i++){
for(auto j:pre[i]){
update(0,0,q,j.a+1,q,j.b);
su+=j.b;
vis[j.a+1]=j.b;
}
llo ind=0;
if(tree[0][2]<=-c[i]){
llo no=0;
pair<llo,llo> cur={0,q};
llo ma=0;
while(cur.a<cur.b){
int mid=(cur.a+cur.b)/2;
llo ok=0;
if(tree[no*2+2][0]-tree[no*2+1][1]<=-c[i]){
ok=1;
}
if(tree[no*2+2][2]<=-c[i]){
ok=1;
}
if(tree[no*2+2][0]-ma<=-c[i]){
ok=1;
}
if(ok==1){
ma=max(ma,tree[no*2+1][1]);
cur={mid+1,cur.b};
no*=2;
no+=2;
continue;
}
cur={cur.a,mid};
no=no*2+1;
}
if(tree[no][0]-ma<=-c[i]){
ind=cur.a;
}
}
llo ind2=0;
if(tree[0][3]>=c[i]){
//ans.pb(c[i]);
llo no=0;
pair<llo,llo> cur={0,q};
llo ma=0;
while(cur.a<cur.b){
/*if(i==2){
cout<<cur.a<<","<<cur.b<<endl;
}*/
/*if(i==1){
cout<<cur.a<<","<<cur.b<<":"<<ma<<endl;
}*/
int mid=(cur.a+cur.b)/2;
push(no,cur.a,cur.b);
push(no*2+1,cur.a,mid);
push(no*2+2,mid+1,cur.b);
llo ok=0;
if(tree[no*2+2][1]-tree[no*2+1][0]>=c[i]){
ok=1;
}
/*if(i==2){
cout<<ok<<','<<endl;
cout<<tree[no*2+2][1]-tree[no*2+1][0]<<"::"<<endl;
}*/
if(tree[no*2+2][3]>=c[i]){
ok=1;
}
/* if(i==2){
cout<<ok<<','<<endl;
}*/
if(tree[no*2+2][1]-ma>=c[i]){
ok=1;
}
/*if(i==2){
cout<<ok<<','<<endl;
}*/
if(ok==1){
ma=min(ma,tree[no*2+1][0]);
cur={mid+1,cur.b};
no*=2;
no+=2;
continue;
}
cur={cur.a,mid};
no=no*2+1;
}
if(i==2){
//cout<<no<<",,"<<endl;
//cout<<tree[no][1]<<",,"<<ma<<endl;
}
if(tree[no][1]-ma>=c[i]){
ind2=cur.a;
}
//cout<<11<<endl;
}
else{
//ans.pb(tree[0][3]);
}
//cout<<i<<":"<<ind<<":"<<ind2<<endl;
//ans.pb(min(su,(llo)c[i]));
llo ind3=0;
llo cot=0;
llo ind4=0;
llo ind5=0;
llo ind6=0;
llo mi=0;
llo ma=0;
llo xx=0;
for(llo j=0;j<=q;j++){
cot+=vis[j];
cot=max(cot,(llo)0);
cot=min(cot,(llo)c[i]);
xx+=vis[j];
if(cot==c[i]){
ind3=max(ind3,j);
}
if(cot==0){
ind4=max(ind4,j);
}
if(xx-mi>=c[i]){
ind5=j;
}
if(xx-ma<=-c[i]){
ind6=j;
}
mi=min(mi,xx);
ma=max(ma,xx);
}
// assert(ind==ind4);
//assert(ind2==ind3);
// cout<<i<<":"<<ind2<<":"<<ind5<<endl;
// assert(ind2==ind5);
// if(ind3>0 and ind5>0){
assert(ind5<=ind3);
// }
ans.pb(cot);
if(ind2>ind){
llo ans2=c[i]+su-query(0,0,q,ind2,ind2);
//ans.pb(ans2);
}
else{
llo ans2=su-query(0,0,q,ind,ind);
//ans.pb(ans2);
}
for(auto j:pre2[i]){
update(0,0,q,j.a+1,q,-j.b);
vis[j.a+1]=0;
su-=j.b;
}
}
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:213:11: warning: unused variable 'ans2' [-Wunused-variable]
213 | llo ans2=c[i]+su-query(0,0,q,ind2,ind2);
| ^~~~
candies.cpp:217:11: warning: unused variable 'ans2' [-Wunused-variable]
217 | llo ans2=su-query(0,0,q,ind,ind);
| ^~~~
candies.cpp:179:13: warning: variable 'ind6' set but not used [-Wunused-but-set-variable]
179 | llo ind6=0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Runtime error |
15 ms |
19540 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5065 ms |
46232 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Runtime error |
127 ms |
76932 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
19464 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Runtime error |
15 ms |
19540 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
