#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;
int idn, idx;
node(){}
node(int at) {
idn=idx=at;
}
node operator+(node B) {
node res=(*this);
if(res.mn>B.mn) {
res.idn=B.idn;
}
if(res.mx<B.mx)res.idx=B.idx;
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(int tl, int tr, int v) {
lz[v]=F();
if(tl==tr) {
t[v]=node(tl);
return;
}
int tm=(tl+tr)/2;
build(tl,tm,2*v);
build(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(){build(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;
st.build();
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, 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;
}
}
node rs=st.query(ress, q+1);
if(rs.idn<rs.idx) {
long long val=rs.mn;
res[i]=st.query(q+1,q+1).mx-val;
}
else if(rs.idn>rs.idx){
long long val=rs.mx;
res[i]=st.query(q+1,q+1).mx-val+c[i];
}
else {
long long tmp=rs.mx;
lo=0,hi=rs.idn;
long long resss=-1;
while(lo<=hi) {
int mid=(lo+hi)/2;
node rrs=st.query(mid,ress);
if(rrs.mx-rrs.mn!=0) {
resss=mid;
lo=mid+1;
}
else {
hi=mid-1;
}
}
if(resss==-1) {
resss=INF;
}
else {
resss=st.query(resss,resss).mx;
}
if(resss<tmp) {
res[i]=st.query(q+1,q+1).mx-tmp+c[i];
}
else {
res[i]=st.query(q+1,q+1).mx-tmp;
}
}
}
return res;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1933 ms |
47548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
