#include "candies.h"
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
namespace trung{
const ll block = 450;
const ll MAXN = 2e5+100;
const ll INF = 1e18;
pll nxt[MAXN][2];
struct event{
ll x,i,v;
};
ll m,n;
namespace segtree{
struct node{
pll min1,max1;
};
const node worst = {MP(INF,-1),MP(-INF,-1)};
node tree[MAXN*4];
ll lazy[MAXN*4];
void push(ll id,ll v){
lazy[id]+=v;
tree[id].min1.fi += v;
tree[id].max1.fi += v;
}
void lz(ll id){
push(id<<1,lazy[id]);
push(id<<1|1,lazy[id]);
lazy[id] = 0;
}
node combine(node x,node y){
node res;
if (y.min1.fi < x.min1.fi)res.min1=y.min1;
else res.min1 = x.min1;
if (y.max1.fi > x.max1.fi)res.max1=y.max1;
else res.max1 = x.max1;
return res;
}
void build(ll id = 1,ll l = 0,ll r = m){
tree[id] = {MP(0,l),MP(0,l)};
if (l < r){
ll mid = (l + r) >> 1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
}
}
void update(ll i,ll v,ll id=1,ll l = 0,ll r = m){
// cout<<id<<' '<<l<<' '<<r<<endl;
if (r < i)return;
if (i <= l){
push(id,v);
return;
}
lz(id);
ll mid = (l + r) >> 1;
update(i,v,id<<1,l,mid);
update(i,v,id<<1|1,mid+1,r);
tree[id] = combine(tree[id<<1],tree[id<<1|1]);
}
node get(ll l1,ll r1,ll id = 1,ll l = 0,ll r = m){
if (l > r1 || l1 > r)return worst;
if (l1 <= l && r <= r1){
return tree[id];
}
lz(id);
ll mid = (l + r) >> 1;
return combine(get(l1,r1,id<<1,l,mid),get(l1,r1,id<<1|1,mid+1,r));
}
node get_last(ll c,node suf = worst,ll id = 1,ll l = 0,ll r = m){
node sus = combine(suf,tree[id]);
if (sus.max1.fi - sus.min1.fi <= c)return sus;
if (l==r){
return sus;
}
ll mid = (l + r) >> 1;
node res = get_last(c,suf,id<<1|1,mid+1,r);
if (res.max1.fi - res.min1.fi <= c)res = get_last(c,res,id<<1,l,mid);
return res;
}
}
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
using namespace trung;
n = c.size();
m = sz(l);
vector <event> all;
for (ll i = 0;i < m;i ++){
all.push_back({l[i],i+1,v[i]});
all.push_back({r[i]+1,i+1,-v[i]});
}
sort(all.begin(),all.end(),[](event a1,event a2){return a1.x < a2.x;});
using namespace segtree;
build();
vector <int> res(n);
for (ll i = 0,ptr = 0;i < n;i ++){
while (ptr < sz(all) && all[ptr].x == i){
update(all[ptr].i,all[ptr].v);
ptr++;
}
node tmp = get_last(c[i]);
if (tmp.max1.fi - tmp.min1.fi <= c[i]){
res[i] = get(m,m).max1.fi;
}
else if (tmp.min1.se > tmp.max1.se){
res[i] = get(m,m).max1.fi - tmp.min1.fi;
}
else{
res[i] = get(m,m).max1.fi - tmp.max1.fi + c[i];
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
274 ms |
41296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
