#include <bits/stdc++.h>
using namespace std;
int mod[800001];
int mx[800001];
int mx2[800001];
int mn[800001];
int mn2[800001];
int C;
void push_sum(int v){
mx2[v<<1]+=mod[v];
mx[v<<1]+= mod[v];
mn2[v<<1]+=mod[v];
mn[v<<1]+= mod[v];
mod[v<<1]+=mod[v];
mx2[v<<1|1]+=mod[v];
mx[v<<1|1]+= mod[v];
mn2[v<<1|1]+=mod[v];
mn[v<<1|1]+= mod[v];
mod[v<<1|1]+=mod[v];
mod[v] = 0;
}
void push_min_max(int v){
mx[v<<1] = min(mx[v],mx[v<<1]);
mn[v<<1] = min(mx[v],mn[v<<1]);
mx[v<<1|1] = min(mx[v],mx[v<<1|1]);
mn[v<<1|1] = min(mx[v],mn[v<<1|1]);
mx[v<<1] = max(mn[v],mx[v<<1]);
mn[v<<1] = max(mn[v],mn[v<<1]);
mx[v<<1|1] = max(mn[v],mx[v<<1|1]);
mn[v<<1|1] = max(mn[v],mn[v<<1|1]);
}
void pull(int v){
if(mx[v<<1] == mx[v<<1|1]){
mx[v] = mx[v<<1];
mx2[v] = max(mx2[v<<1],mx2[v<<1|1]);
}
else if(mx[v<<1] < mx[v<<1|1]){
mx[v] = mx[v<<1|1];
mx2[v] = max(mx[v<<1],mx2[v<<1|1]);
}
else{
mx[v] = mx[v<<1];
mx2[v] = max(mx2[v<<1],mx[v<<1|1]);
}
if(mn[v<<1] == mn[v<<1|1]){
mn[v] = mn[v<<1];
mn2[v] = min(mn2[v<<1],mn2[v<<1|1]);
}
else if(mn[v<<1] > mn[v<<1|1]){
mn[v] = mn[v<<1|1];
mn2[v] = min(mn[v<<1],mn2[v<<1|1]);
}
else{
mn[v] = mn[v<<1];
mn2[v] = min(mn2[v<<1],mn[v<<1|1]);
}
}
void push(int v){
push_sum(v);
//push_min_max(v);
}
void update_add(int v,int l,int r,int tl,int tr,int val){
if(r < tl or tr < l) return;
if(tl <= l and r <= tr){
mx[v]+=val;
mx2[v]+=val;
mn2[v]+=val;
mn[v]+=val;
mod[v]+=val;
return;
}
push(v);
int m = (l+r)/2;
update_add(v<<1,l,m,tl,tr,val);
update_add(v<<1|1,m+1,r,tl,tr,val);
//pull(v);
}
void update_max(int v,int l,int r){
if(mx[v] <= C) return;
if(mx[v] > C and mx2[v] < C){
mx[v] = C;
mn2[v] = min(mn2[v],C);
mn[v] = min(mn[v],C);
return;
}
push(v);
int m = (l+r)/2;
update_max(v<<1,l,m);
update_max(v<<1|1,m+1,r);
pull(v);
}
void update_min(int v,int l,int r){
if(mn[v] >= 0) return;
if(mn[v] < 0 and mn2[v] > 0){
mn[v] = 0;
mx2[v] = max(mx2[v],0);
mx[v] = max(mx[v],0);
return;
}
push(v);
int m = (l+r)/2;
update_min(v<<1,l,m);
update_min(v<<1|1,m+1,r);
pull(v);
}
vector<int> blds(int v,int l,int r){
if(l == r){
return {mx[v]};
}
push(v);
int m = (l+r)/2;
vector<int> a = blds(v<<1,l,m);
vector<int> b = blds(v<<1|1,m+1,r);
for(auto e:b) a.push_back(e);
return a;
}
vector<int> distribute_candies(vector<int> C_, vector<int> L, vector<int> R, vector<int> V) {
C = 1e9;
int n = C_.size();
for (int i = 0; i < 4*n; ++i)
{
mod[i] = 0;
}
for (int i = 0; i < L.size(); ++i)
{
update_add(1,0,n-1,L[i],R[i],V[i]);
//vector<int> tmp = blds(1,0,n-1);
//for(int j = 0; j < 4*n;j++) cout << mn[j] << " ";
//cout << "\n";
}
vector<int> tmp = blds(1,0,n-1);
for(int i = 0;i < n;i++) tmp[i] = min(tmp[i],C_[i]);
return tmp;
}
Compilation message
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:134:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for (int i = 0; i < L.size(); ++i)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
198 ms |
24296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
312 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 |
0 ms |
316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
