#include "candies.h"
#include <vector>
using namespace std;
typedef long long ll;
const ll maxn=2e5+10;
const ll inf=1e9+10;
struct node{
ll min,max,lazy;
};
ll n,q,val=0;
vector<pair<ll,ll> > events[maxn];
vector<int> vv;
node segt[4*maxn];
void ispisi(node a){
//cout<<a.min<<" "<<a.max<<" "<<a.lazy<<"\n";
}
node comb(node a,node b){
node ret;
ret.lazy=0;
ret.max=max(a.max,b.max);
ret.min=min(a.min,b.min);
return ret;
}
void push(ll ind,ll l,ll r){
if(segt[ind].lazy==0) return;
if(l!=r){
segt[2*ind].min+=segt[ind].lazy; segt[2*ind].max+=segt[ind].lazy;
segt[2*ind+1].min+=segt[ind].lazy; segt[2*ind+1].max+=segt[ind].lazy;
segt[2*ind].lazy+=segt[ind].lazy;
segt[2*ind+1].lazy+=segt[ind].lazy;
}
segt[ind].lazy=0;
}
void update(ll tl,ll tr,ll v,ll ind=1,ll l=0,ll r=q-1){
push(ind,l,r);
if(tl<=l && r<=tr){
segt[ind].lazy+=v;
segt[ind].min+=v;
segt[ind].max+=v;
return;
}
ll mid=l+(r-l)/2;
if(tl<=mid) update(tl,tr,v,2*ind,l,mid);
if(tr>mid) update(tl,tr,v,2*ind+1,mid+1,r);
segt[ind]=comb(segt[2*ind],segt[2*ind+1]);
}
node qr(ll tl,ll tr,ll ind=1,ll l=0,ll r=q-1){
if(tl<=l && r<=tr){
return segt[ind];
} push(ind,l,r);
ll mid=l+(r-l)/2;
node ret={inf,-inf,0};
if(tl<=mid) ret=comb(ret,qr(tl,tr,2*ind,l,mid));
if(tr>mid) ret=comb(ret,qr(tl,tr,2*ind+1,mid+1,r));
return ret;
}
ll query(ll c){
ll ind=1,l=0,r=q-1,res=-1;
ll tmax=-inf,tmin=inf;
/*while(true){ //trazim prvi na kome je razlika <=c
if(l==r){
if(max(tmax,segt[ind].max)-min(tmin,segt[ind].min)<=c){
res=l;
tmax=max(tmax,segt[ind].max);
tmin=min(tmin,segt[ind].min);
}
break;
}
if(max(tmax,segt[2*ind+1].max)-min(tmin,segt[2*ind+1].min)<=c){
res=l+(r-l)/2+1;
r=l+(r-l)/2;
tmax=max(tmax,segt[2*ind+1].max);
tmin=min(tmin,segt[2*ind+1].min);
ind=2*ind;
}else{
ind=2*ind+1;
l=l+(r-l)/2+1;
}
}*/
while(l<=r){
int mid=l+(r-l)/2;
if(qr(mid,q-1).max-qr(mid,q-1).min<=c){
res=mid;
r=mid-1;
}else{
l=mid+1;
}
}
tmax=qr(res,q-1).max;
tmin=qr(res,q-1).min;
if(vv[res]>0){
return val-(tmax-c);
}else{
return val-tmin;
}
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n=c.size();
q=l.size()+2;
l.insert(l.begin(),0); l.insert(l.begin(),0);
r.insert(r.begin(),n-1); r.insert(r.begin(),n-1);
v.insert(v.begin(),-inf); v.insert(v.begin(),inf);
vv=v;
for(ll i=0;i<q;i++){
events[l[i]].push_back({i,v[i]});
events[r[i]+1].push_back({i,-v[i]});
}
vector<int> ans(n);
for(ll i=0;i<n;i++){
for(auto event:events[i]){
val+=event.second;
update(event.first,q-1,event.second);
}
ans[i]=query(c[i]);
}
return ans;
}
Compilation message
candies.cpp: In function 'll query(ll)':
candies.cpp:71:8: warning: unused variable 'ind' [-Wunused-variable]
71 | ll ind=1,l=0,r=q-1,res=-1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1582 ms |
36364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
275 ms |
33884 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
149 ms |
32596 KB |
Output is correct |
| 4 |
Correct |
516 ms |
8952 KB |
Output is correct |
| 5 |
Correct |
1389 ms |
35560 KB |
Output is correct |
| 6 |
Correct |
1370 ms |
36288 KB |
Output is correct |
| 7 |
Incorrect |
1261 ms |
36776 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
