#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
struct Node{
int cntmx, cntmn;
int64_t lazy, mx1, mx2, mn1, mn2;
Node(){
mx1 = mx2 = (int64_t)-1e18;
mn1 = mn2 = (int64_t)1e18;
cntmn = cntmx = lazy = 0;
}
Node(int v){
mx1 = mn1 = v;
mn2 = (int)1e9 + 15, mx2 = (int)-1e9;
cntmn = cntmx = 1;
lazy = 0;
}
};
int n = c.size(), q = (int)l.size(), k = c[0];
vector<int> a(n);
vector<Node> tree(4 * n + 15);
auto mrg = [&](Node &a, Node &b){
Node ret;
if(a.mn1 == b.mn1){
ret.mn1 = a.mn1, ret.mn2 = min(a.mn2, b.mn2), ret.cntmn = a.cntmn + b.cntmn;
}
else if(a.mn1 < b.mn1){
ret.mn1 = a.mn1, ret.mn2 = min(b.mn1, a.mn2), ret.cntmn = a.cntmn;
}
else{
ret.mn1 = b.mn1, ret.mn2 = min(b.mn2, a.mn1), ret.cntmn = b.cntmn;
}
if(a.mx1 == b.mx1){
ret.mx1 = a.mx1, ret.mx2 = max(a.mx2, b.mx2), ret.cntmx = a.cntmx + b.cntmx;
}
else if(a.mx1 > b.mx1){
ret.mx1 = a.mx1, ret.mx2 = max(a.mx2, b.mx1), ret.cntmx = a.cntmx;
}
else{
ret.mx1 = b.mx1, ret.mx2 = max(a.mx1, b.mx2), ret.cntmx = b.cntmx;
}
return ret;
};
function<void(int, int, int)> build = [&](int s, int e, int node){
if(s == e){
tree[node] = Node(0);
return;
}
int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
build(s, md, lx), build(md + 1, e, rx);
tree[node] = mrg(tree[lx], tree[rx]);
};
auto lz_add = [&](int s, int e, int node, int64_t val){
if(!val)return;
tree[node].mn1 += val, tree[node].mx1 += val;
if(tree[node].cntmx != e - s + 1)tree[node].mx2 += val;
if(tree[node].cntmn != e - s + 1)tree[node].mn2 += val;
tree[node].lazy += val;
};
auto lz_mn = [&](int s, int e, int node, int64_t val){
if(tree[node].mx1 <= val)return;
tree[node].mx1 = val;
if(tree[node].cntmn == e - s + 1){
tree[node].mn1 = val;
}
else if(tree[node].mn2 > val){
tree[node].mn2 = val;
}
};
auto lz_mx = [&](int s, int e, int node, int64_t val){
if(tree[node].mn1 >= val)return;
tree[node].mn1 = val;
if(tree[node].cntmx == e - s + 1){
tree[node].mx1 = val;
}
else if(tree[node].mx2 < val){
tree[node].mx2 = val;
}
};
auto lz = [&](int s, int e, int node){
if(s == e)return;
int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
lz_add(s, md, lx, tree[node].lazy), lz_add(md + 1, e, rx, tree[node].lazy);
tree[node].lazy = 0;
lz_mn(s, md, lx, tree[node].mx1), lz_mn(md + 1, e, rx, tree[node].mx1);
lz_mx(s, md, lx, tree[node].mn1), lz_mx(md + 1, e, rx, tree[node].mn1);
};
function<void(int, int, int, int, int, int)> update_add = [&](int s, int e, int node, int l, int r, int val){
lz(s, e, node);
if(s > r || e < l)return;
if(l <= s && e <= r){
lz_add(s, e, node, val);
return;
}
int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
update_add(s, md, lx, l, r, val), update_add(md + 1, e, rx, l, r, val);
tree[node] = mrg(tree[lx], tree[rx]);
};
function<void(int, int, int, int, int, int)> update_mn = [&](int s, int e, int node, int l, int r, int val){
lz(s, e, node);
if(s > r || e < l || tree[node].mx1 <= val)return;
if(l <= s && e <= r && tree[node].mx2 < val){
lz_mn(s, e, node, val);
return;
}
int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
update_mn(s, md, lx, l, r, val), update_mn(md + 1, e, rx, l, r, val);
tree[node] = mrg(tree[lx], tree[rx]);
};
function<void(int, int, int, int, int, int)> update_mx = [&](int s, int e, int node, int l, int r, int val){
lz(s, e, node);
if(s > r || e < l || tree[node].mn1 >= val)return;
if(l <= s && e <= r && tree[node].mn2 > val){
lz_mx(s, e, node, val);
return;
}
int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
update_mx(s, md, lx, l, r, val), update_mx(md + 1, e, rx, l, r, val);
tree[node] = mrg(tree[lx], tree[rx]);
};
function<void(int, int, int)> go = [&](int s, int e, int node){
if(s == e){
a[s] = tree[node].mx1;
return;
}
lz(s, e, node);
int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
go(s, md, lx), go(md + 1, e, rx);
tree[node] = mrg(tree[lx], tree[rx]);
};
build(0, n - 1, 1);
for(int i = 0; i < q; i++){
update_add(0, n - 1, 1, l[i], r[i], v[i]);
if(v[i] > 0){
update_mn(0, n - 1, 1, l[i], r[i], k);
}
else{
update_mx(0, n - 1, 1, l[i], r[i], 0);
}
}
go(0, n - 1, 1);
return a;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
644 ms |
49744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
192 ms |
8420 KB |
Output is correct |
| 3 |
Correct |
62 ms |
42580 KB |
Output is correct |
| 4 |
Correct |
492 ms |
50988 KB |
Output is correct |
| 5 |
Correct |
610 ms |
51280 KB |
Output is correct |
| 6 |
Correct |
784 ms |
51672 KB |
Output is correct |
| 7 |
Correct |
773 ms |
50928 KB |
Output is correct |
| # |
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 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
