#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
int lim;
const int INF = 1e9;
struct node{
int maxi,max2,mini,min2,lazy;
node():maxi(0),max2(-INF),mini(0),min2(INF),lazy(0){}
node(node left,node right):maxi(0),max2(-INF),mini(0),min2(INF),lazy(0){
maxi = max(left.maxi,right.maxi);
if(left.maxi!=maxi)max2=max(max2,left.maxi);
else max2=max(max2,left.max2);
if(right.maxi!=maxi)max2=max(max2,right.maxi);
else max2=max(max2,right.max2);
mini = min(left.mini,right.mini);
if(left.mini!=mini)min2=min(min2,left.mini);
else min2=min(min2,left.min2);
if(right.mini!=mini)min2=min(min2,right.mini);
else min2=min(min2,right.min2);
}
bool applylazy(){
mini+=lazy;
min2+=lazy;
maxi+=lazy;
max2+=lazy;
if(lazy<0){
if(min2<0)return false;
mini=max(mini,0);
max2=max(max2,0);
maxi=max(maxi,0);
return true;
} else {
if(max2>lim)return false;
maxi=min(lim,maxi);
min2=min(lim,min2);
mini=min(lim,mini);
return true;
}
}
};
struct segtree{
vector<node> tree;
int n;
segtree(int n):n(n),tree(4*n){}
void update(int qX,int qL,int qR,int L,int R,int x){
if(tree[x].lazy){
tree[x].applylazy();
if(L!=R){
tree[2*x].lazy+=qX;
tree[2*x+1].lazy+=qX;
}
tree[x].lazy=0;
}
if(qR<L or R<qL)return;
if(qL<=L and R<=qR){
tree[x].lazy=qX;
if(tree[x].applylazy()){
if(L!=R){
tree[2*x].lazy+=qX;
tree[2*x+1].lazy+=qX;
}
tree[x].lazy=0;
return;
}
tree[x].lazy=0;
}
int mid = (L+R)/2;
update(qX,qL,qR,L,mid,2*x);
update(qX,qL,qR,mid+1,R,2*x+1);
tree[x]={tree[2*x],tree[2*x+1]};
}
void update(int qX,int qL,int qR){
update(qX,qL,qR,1,n,1);
}
int get(int qX,int L,int R,int x){
if(qX<L or R<qX)return 0;
if(tree[x].lazy){
tree[x].applylazy();
if(L!=R){
tree[2*x].lazy+=qX;
tree[2*x+1].lazy+=qX;
}
tree[x].lazy=0;
}
if(L==R){
return tree[x].maxi;
}
int mid = (L+R)/2;
return get(qX,L,mid,2*x)+get(qX,mid+1,R,2*x+1);
}
int get(int qX){
return get(qX,1,n,1);
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v){
int n = c.size();
int q = v.size();
lim = c[0];
segtree seg(n);
for(int i=0;i<q;i++){
seg.update(v[i],l[i]+1,r[i]+1);
}
vector<int> s(n);
for(int i=0;i<n;i++)s[i]=seg.get(i+1);
return s;
}
Compilation message
candies.cpp: In constructor 'segtree::segtree(int)':
candies.cpp:46:9: warning: 'segtree::n' will be initialized after [-Wreorder]
46 | int n;
| ^
candies.cpp:45:18: warning: 'std::vector<node> segtree::tree' [-Wreorder]
45 | vector<node> tree;
| ^~~~
candies.cpp:47:5: warning: when initialized here [-Wreorder]
47 | segtree(int n):n(n),tree(4*n){}
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
208 ms |
23016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
