#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) {
int n = c.size(), q = (int)l.size(), k = c[0];
vector<int> a(n);
if(n <= 2000 && q <= 2000){
for(int i = 0; i < q; i++){
for(int j = l[i]; j <= r[i]; j++){
a[j] += v[i];
a[j] = max(a[j], 0);
a[j] = min(a[j], c[j]);
}
}
return a;
}
if(*min_element(v.begin(), v.end()) >= 0){
vector<int64_t> pref(n + 1);
for(int i = 0; i < q; i++){
pref[l[i]] += v[i];
pref[r[i] + 1] -= v[i];
}
for(int i = 0; i < n; i++){
pref[i + 1] += pref[i];
a[i] = min(pref[i], (int64_t)c[i]);
}
return a;
}
if(*min_element(c.begin(), c.end()) == *max_element(c.begin(), c.end())){
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;
}
else{
int n = c.size(), q = (int)l.size();
vector<int> a(n);
vector<pair<int, int>> arr(n);
for(int i = 0; i < n; i++){
arr[i] = {c[i], i};
}
sort(arr.begin(), arr.end());
struct Node{
//mx1 is ai, mx2 is ci - ai
int64_t mx1, mx2, lazy;
//0 nothing, 1 to full, 2 to empty
int lazy2;
int full_mx1, full_mx2;
int empty_mx1, empty_mx2;
Node(){
mx1 = mx2 = lazy = 0;
full_mx1 = full_mx2 = empty_mx1 = empty_mx2 = 0;
}
Node(int c){
mx1 = 0, mx2 = c, lazy = 0;
full_mx1 = c;
full_mx2 = 0;
empty_mx1 = 0;
empty_mx2 = c;
}
};
vector<Node> tree(4 * n + 15);
auto mrg = [&](Node &a, Node &b){
Node ret;
ret.mx1 = max(a.mx1, b.mx1);
ret.mx2 = max(a.mx2, b.mx2);
ret.full_mx1 = max(a.full_mx1, b.full_mx1);
ret.full_mx2 = max(a.full_mx2, b.full_mx2);
ret.empty_mx1 = max(a.empty_mx1, b.empty_mx1);
ret.empty_mx2 = max(a.empty_mx2, b.empty_mx2);
return ret;
};
function<void(int, int, int)> build = [&](int s, int e, int node){
if(s == e){
tree[node] = Node(arr[s].first);
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 = [&](int s, int e, int node){
if(tree[node].lazy2){
if(tree[node].lazy2 == 1){
tree[node].mx1 = tree[node].full_mx1;
tree[node].mx2 = tree[node].full_mx2;
}
else{
tree[node].mx1 = tree[node].empty_mx1;
tree[node].mx2 = tree[node].empty_mx2;
}
if(s != e){
int lx = node * 2, rx = node * 2 + 1;
tree[lx].lazy = tree[rx].lazy = 0;
tree[lx].lazy2 = tree[rx].lazy2 = tree[node].lazy2;
}
tree[node].lazy2 = 0;
}
if(tree[node].lazy){
tree[node].mx1 += tree[node].lazy, tree[node].mx2 -= tree[node].lazy;
if(s != e){
int lx = node * 2, rx = node * 2 + 1;
tree[lx].lazy += tree[node].lazy, tree[rx].lazy += tree[node].lazy;
}
tree[node].lazy = 0;
}
};
function<int(int, int, int, int)> get_empty = [&](int s, int e, int node, int val){
lz(s, e, node);
if(s == e){
return (tree[node].mx1 + val > 0 ? s - 1 : s);
}
int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
lz(s, md, lx);
if(tree[lx].mx1 + val <= 0)return get_empty(md + 1, e, rx, val);
else return get_empty(s, md, lx, val);
};
function<int(int, int, int, int)> get_full = [&](int s, int e, int node, int val){
lz(s, e, node);
if(s == e){
return (tree[node].mx2 - val > 0 ? s - 1 : s);
}
int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
lz(s, md, lx);
if(tree[lx].mx2 - val <= 0)return get_full(md + 1, e, rx, val);
else return get_full(s, md, lx, val);
};
function<void(int, int, int, int, int)> update_pref = [&](int s, int e, int node, int i, int type){
lz(s, e, node);
if(s > i)return;
if(e <= i){
tree[node].lazy2 = type;
lz(s, e, node);
return;
}
int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
update_pref(s, md, lx, i, type), update_pref(md + 1, e, rx, i, type);
tree[node] = mrg(tree[lx], tree[rx]);
};
function<void(int, int, int, int, int)> update_suf = [&](int s, int e, int node, int i, int val){
lz(s, e, node);
if(e < i)return;
if(s >= i){
tree[node].lazy = val;
lz(s, e, node);
return;
}
int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
update_suf(s, md, lx, i, val), update_suf(md + 1, e, rx, i, val);
tree[node] = mrg(tree[lx], tree[rx]);
};
function<void(int, int, int)> go = [&](int s, int e, int node){
lz(s, e, node);
if(s == e){
a[arr[s].second] = tree[node].mx1;
return;
}
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++){
if(v[i] > 0){
int j = get_full(0, n - 1, 1, v[i]);
update_pref(0, n - 1, 1, j, 1);
update_suf(0, n - 1, 1, j + 1, v[i]);
}
else{
int j = get_empty(0, n - 1, 1, v[i]);
update_pref(0, n - 1, 1, j, 2);
update_suf(0, n - 1, 1, j + 1, v[i]);
}
}
go(0, n - 1, 1);
return a;
}
}
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:5:42: warning: unused variable 'k' [-Wunused-variable]
5 | int n = c.size(), q = (int)l.size(), k = c[0];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
13652 KB |
Output is correct |
| 2 |
Correct |
65 ms |
13136 KB |
Output is correct |
| 3 |
Correct |
66 ms |
12868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
189 ms |
8528 KB |
Output is correct |
| 3 |
Correct |
61 ms |
43348 KB |
Output is correct |
| 4 |
Correct |
518 ms |
51768 KB |
Output is correct |
| 5 |
Correct |
566 ms |
52024 KB |
Output is correct |
| 6 |
Correct |
800 ms |
52408 KB |
Output is correct |
| 7 |
Correct |
681 ms |
51764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
169 ms |
8020 KB |
Output is correct |
| 4 |
Correct |
88 ms |
43860 KB |
Output is correct |
| 5 |
Correct |
326 ms |
50928 KB |
Output is correct |
| 6 |
Correct |
315 ms |
51508 KB |
Output is correct |
| 7 |
Correct |
341 ms |
52180 KB |
Output is correct |
| 8 |
Correct |
306 ms |
50768 KB |
Output is correct |
| 9 |
Correct |
62 ms |
13872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
348 KB |
Output is correct |
| 6 |
Correct |
73 ms |
13652 KB |
Output is correct |
| 7 |
Correct |
65 ms |
13136 KB |
Output is correct |
| 8 |
Correct |
66 ms |
12868 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
189 ms |
8528 KB |
Output is correct |
| 11 |
Correct |
61 ms |
43348 KB |
Output is correct |
| 12 |
Correct |
518 ms |
51768 KB |
Output is correct |
| 13 |
Correct |
566 ms |
52024 KB |
Output is correct |
| 14 |
Correct |
800 ms |
52408 KB |
Output is correct |
| 15 |
Correct |
681 ms |
51764 KB |
Output is correct |
| 16 |
Correct |
0 ms |
344 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
169 ms |
8020 KB |
Output is correct |
| 19 |
Correct |
88 ms |
43860 KB |
Output is correct |
| 20 |
Correct |
326 ms |
50928 KB |
Output is correct |
| 21 |
Correct |
315 ms |
51508 KB |
Output is correct |
| 22 |
Correct |
341 ms |
52180 KB |
Output is correct |
| 23 |
Correct |
306 ms |
50768 KB |
Output is correct |
| 24 |
Correct |
62 ms |
13872 KB |
Output is correct |
| 25 |
Correct |
1 ms |
604 KB |
Output is correct |
| 26 |
Incorrect |
72 ms |
43732 KB |
Output isn't correct |
| 27 |
Halted |
0 ms |
0 KB |
- |
