#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
const int N_=200'010;
const long long INF=1e18;
struct node {
long long mn=0, mx=0;
node operator+(node B) {
node res;
res.mn=mn;
res.mx=mx;
res.mn=min(res.mn, B.mn);
res.mx=max(res.mx, B.mx);
return res;
}
};
struct F1 {
long long add=0;
F1(){}
node applyAggregate(node res) {
res.mn+=add;
res.mx+=add;
return res;
}
void compose(F1 par) {
add+=par.add;
}
};
template<typename T, typename F>
struct ST {
vector<T> t;
vector<F> lz;
T def;
int n;
ST(){}
ST(int N) {
n=N;
t=vector<T>(4*n);
lz=vector<F>(4*n);
}
void build(T a[], int tl, int tr, int v) {
lz[v]=F(tl,tr);
if(tl==tr) {
t[v]=a[tl];
return;
}
int tm=(tl+tr)/2;
build(a,tl,tm,2*v);
build(a,tm+1,tr,2*v+1);
t[v]=t[2*v]+t[2*v+1];
}
void push(int v) {
lz[2*v].compose(lz[v]);
lz[2*v+1].compose(lz[v]);
t[v]=lz[v].applyAggregate(t[v]);
lz[v]=F();
}
T query(int l, int r, int tl, int tr, int v) {
if(l>tr or r<tl)return def;
if(l<=tl and tr<=r)return lz[v].applyAggregate(t[v]);
push(v);
int tm=(tl+tr)/2;
return query(l,r,tl,tm,2*v)+query(l,r,tm+1,tr,2*v+1);
}
void update(int l, int r, F upd, int tl, int tr, int v) {
if(r<tl or tr<l)return;
if(l<=tl and tr<=r) {
lz[v].compose(upd);
return;
}
int tm=(tl+tr)/2;
push(v);
update(l,r,upd,tl,tm,2*v);
update(l,r,upd,tm+1,tr,2*v+1);
t[v]=lz[2*v].applyAggregate(t[2*v])+lz[2*v+1].applyAggregate(t[2*v+1]);
}
void update(int at, T val, int tl, int tr, int v) {
if(tl==tr) {
t[v]=val;
lz[v]=F();
return;
}
int tm=(tl+tr)/2;
push(v);
if(at<=tm)update(at,val,tl,tm,2*v);
else update(at,val,tm+1,tr,2*v+1);
t[v]=lz[2*v].applyAggregate(t[2*v])+lz[2*v+1].applyAggregate(t[2*v+1]);
}
T query(int l, int r){return query(l,r,0,n-1,1);}
void update(int l, int r, F upd){update(l,r,upd,0,n-1,1);}
void update(int at, T val){update(at,val,0,n-1,1);}
void build(T a[]){build(a,0,n-1,1);}
};
vector<int32_t> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n=c.size(), q=l.size();
ST<node, F1> st(q+2);
st.def.mx=-INF;
st.def.mn=INF;
vector<int32_t> res(n);
vector<pair<int,long long>> ad[n+1];
for(int i=0;i<q;i++) {
ad[l[i]].push_back({i+1,v[i]});
ad[r[i]+1].push_back({i+1,-v[i]});
}
for(int i = 0;i<n;i++) {
for(auto to:ad[i]) {
F1 lz;
lz.add=to.second;
st.update(to.first, q+1, lz);
}
int lo=0, hi=q+1;
long long ress=0;
while(lo<=hi) {
int mid=(lo+hi)/2;
node rs=st.query(mid, q+1);
if(rs.mx-rs.mn<=c[i]) {
ress=mid;
hi=mid-1;
}
else {
lo=mid+1;
}
}
long long cur=st.query(ress,ress).mx;
lo=0,hi=ress-1;
long long resss=-1;
while(lo<=hi) {
int mid=(lo+hi)/2;
node rs=st.query(mid,ress);
if(rs.mx-rs.mn!=0) {
resss=mid;
lo=mid+1;
}
else {
hi=mid-1;
}
}
if(resss==-1) {
resss=INF;
}
else {
resss=st.query(resss,resss).mx;
}
if(cur==st.query(q+1,q+1).mx) {
if(resss>cur) {
res[i]=st.query(q+1,q+1).mx-(cur);
}
else {
res[i]=st.query(q+1,q+1).mx-(cur)+c[i];
}
}
else {
resss=st.query(q+1,q+1).mx;
if(resss>cur) {
res[i]=st.query(q+1,q+1).mx-(cur);
}
else {
res[i]=st.query(q+1,q+1).mx-(cur)+c[i];
}
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
304 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
296 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1927 ms |
46132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
304 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
296 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
