#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();
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
176 ms |
51284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
169 ms |
8016 KB |
Output is correct |
| 4 |
Correct |
76 ms |
43060 KB |
Output is correct |
| 5 |
Correct |
347 ms |
50012 KB |
Output is correct |
| 6 |
Correct |
350 ms |
50772 KB |
Output is correct |
| 7 |
Correct |
330 ms |
51308 KB |
Output is correct |
| 8 |
Correct |
349 ms |
49832 KB |
Output is correct |
| 9 |
Correct |
156 ms |
51296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
