#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define INF 1000000000000000007
#define F first
#define S second
#define pb push_back
#define ll long long
typedef pair<ll,pair<pair<ll,ll>, pair<ll,ll> > > pa;
ll n,q,a[MAXN];
vector<pair<ll,ll> > vec;
vector<ll> add[MAXN],del[MAXN];
struct node{
ll mx,mi,pmx,pmi,val;
node *l, *r;
node() : pmx(-1),pmi(-1),mx(-INF),mi(INF),val(0),l(NULL),r(NULL) {}
node(node *_l,node *_r) : pmx(-1),pmi(-1),mx(-INF),mi(INF),val(0),l(_l),r(_r) {}
} *top;
node *build(ll be,ll ed){
if(be == ed) return new node();
ll mid = (be+ed)/2;
return new node(build(be,mid),build(mid+1,ed));
}
void update(node *pos,ll be,ll ed,ll i,ll x){
if(be > ed || i < be || ed < i) return;
if(be == ed){
pos->val += x;
pos->mx = pos->val, pos->pmx = be;
pos->mi = pos->val, pos->pmi = be;
return;
}
ll mid = (be+ed)/2;
update(pos->l,be,mid,i,x), update(pos->r,mid+1,ed,i,x);
pos->val = pos->l->val + pos->r->val;
pos->mx = max(pos->l->mx, pos->l->val + pos->r->mx);
pos->pmx = pos->l->mx > (pos->l->val + pos->r->mx) ? pos->l->pmx : pos->r->pmx;
pos->mi = min(pos->l->mi, pos->l->val + pos->r->mi);
pos->pmi = pos->l->mi < (pos->l->val + pos->r->mi) ? pos->l->pmi : pos->r->pmi;
}
pa query(node *pos,ll be,ll ed,ll x,ll y){
if(be > ed || ed < x || y < be) return {0,{{-INF,-1},{INF,-1}}};
if(x <= be && ed <= y){
return {pos->val,{{pos->mx,pos->pmx},{pos->mi,pos->pmi}}};
};
ll mid = (be+ed)/2;
pa L = query(pos->l,be,mid,x,y), R = query(pos->r,mid+1,ed,x,y);
return {L.F+R.F,{{max(L.S.F.F,L.F + R.S.F.F), (L.S.F.F > L.F + R.S.F.F) ? L.S.F.S : R.S.F.S},{min(L.S.S.F,L.F + R.S.S.F), (L.S.S.F < L.F + R.S.S.F) ? L.S.S.S : R.S.S.S}}};
}
ll remain(ll c,ll all){
ll be = 1, ed = all+2,val = 0;
while(be <= ed){
ll mid = (be+ed)/2;
pa p = query(top,1,all+2,mid,all+2);
ll va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
//printf("OOO %d %d %d : %d %d\n",be,mid,ed,mx,mi);
if(mx-mi > c) be = mid+1;
else ed = mid-1;
}
//printf("|| %d %d\n",c,ed);
pa p = query(top,1,all+2,ed,all+2);
int va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
val = query(top,1,all+2,max(px,pi)+1,all+2).F;
if(px > pi) val += c;
//printf(">>>>> %d %d , %d\n",px,pi,val);
return val;
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
int n = c.size(), q = l.size();
for(int i=1;i<=n;i++) a[i] = c[i-1];
for(int i=0;i<q;i++){
l[i]++, r[i]++;
add[l[i]].pb(i), del[r[i]].pb(i);
}
vector<int> ans;
top = build(1,q+2);
update(top,1,q+2,1,1e9);
update(top,1,q+2,2,-1e9);
for(int i=1;i<=n;i++){
for(auto id : add[i]){
update(top,1,q+2,id+3,v[id]);
}
// for(int j=1;j<=q+2;j++){
// printf("(%d,%d) ",query(top,1,q+2,j,q+2).S.F.F,query(top,1,q+2,j,q+2).S.S.F);
// }
printf("\n\n");
ans.pb(remain(a[i],q));
for(auto id : del[i]){
update(top,1,q+2,id+3,-v[id]);
}
}
return ans;
}
Compilation message
candies.cpp: In constructor 'node::node()':
candies.cpp:15:18: warning: 'node::pmi' will be initialized after [-Wreorder]
15 | ll mx,mi,pmx,pmi,val;
| ^~~
candies.cpp:15:8: warning: 'long long int node::mx' [-Wreorder]
15 | ll mx,mi,pmx,pmi,val;
| ^~
candies.cpp:17:5: warning: when initialized here [-Wreorder]
17 | node() : pmx(-1),pmi(-1),mx(-INF),mi(INF),val(0),l(NULL),r(NULL) {}
| ^~~~
candies.cpp: In constructor 'node::node(node*, node*)':
candies.cpp:15:18: warning: 'node::pmi' will be initialized after [-Wreorder]
15 | ll mx,mi,pmx,pmi,val;
| ^~~
candies.cpp:15:8: warning: 'long long int node::mx' [-Wreorder]
15 | ll mx,mi,pmx,pmi,val;
| ^~
candies.cpp:18:5: warning: when initialized here [-Wreorder]
18 | node(node *_l,node *_r) : pmx(-1),pmi(-1),mx(-INF),mi(INF),val(0),l(_l),r(_r) {}
| ^~~~
candies.cpp: In function 'long long int remain(long long int, long long int)':
candies.cpp:60:12: warning: unused variable 'va' [-Wunused-variable]
60 | ll va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
| ^~
candies.cpp:60:36: warning: unused variable 'px' [-Wunused-variable]
60 | ll va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
| ^~
candies.cpp:60:64: warning: unused variable 'pi' [-Wunused-variable]
60 | ll va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
| ^~
candies.cpp:68:9: warning: unused variable 'va' [-Wunused-variable]
68 | int va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
| ^~
candies.cpp:68:19: warning: unused variable 'mx' [-Wunused-variable]
68 | int va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
| ^~
candies.cpp:68:47: warning: unused variable 'mi' [-Wunused-variable]
68 | int va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5332 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5332 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
87 ms |
24220 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
435 ms |
39456 KB |
Output is correct |
| 3 |
Runtime error |
32 ms |
16900 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5028 KB |
Output is correct |
| 3 |
Correct |
159 ms |
37840 KB |
Output is correct |
| 4 |
Runtime error |
30 ms |
14720 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5332 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5332 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 6 |
Runtime error |
87 ms |
24220 KB |
Execution killed with signal 11 |
| 7 |
Halted |
0 ms |
0 KB |
- |
