#include <bits/stdc++.h>
//#include "grader.cpp"
#include "candies.h"
#define F first
#define S second
#define pb push_back
#define sz(x) (int)x.size()
#define el "\n"
#define all(x) (x).begin(), (x).end()
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
struct st_beats {
struct node {
ll mx, mn;
ll D, Dx;
node() {
mx = mn = D = 0;
Dx = -2e9;
}
node operator +(node other) {
node ret;
ret.mx = max(mx, other.mx);
ret.mn = min(mn, other.mn);
return ret;
}
void mrg(node &a, node &b) {
node x = a + b;
mx = x.mx; mn = x.mn;
}
void add() {
mx += D; mn += D;
}
void updL() {
mx = mn = Dx;
Dx = -2e9;
}
};
vector <node> t;
int n, h;
st_beats() {}
void init(int _n, int _h) {
t.resize(8 * _n);
for (int i = 0; i < sz(t); i++) {
t[i] = node();
}
h = _h;
n = _n;
}
void push(int v) {
if (t[v].D) {
t[v].add();
t[v * 2].D += t[v].D;
t[v * 2 + 1].D += t[v].D;
t[v].D = 0;
}
}
void pushL(int v) {
if (t[v].Dx != -2e9) {
t[v * 2].Dx = t[v].Dx;
t[v * 2 + 1].Dx = t[v].Dx;
t[v * 2].D = t[v * 2 + 1].D = 0;
t[v].updL();
}
}
void psh(int v) {
pushL(v);
push(v);
}
void upd(int v, int l, int r, int tl, int tr, int val) {
psh(v);
if (l > r || tl > tr || tl > r || l > tr) {
return;
}
int md = (l + r) >> 1;
if (l >= tl && r <= tr) {
t[v].D += val;
psh(v);
return;
}
upd(v * 2, l, md, tl, tr, val);
upd(v * 2 + 1, md + 1, r, tl, tr, val);
t[v].mrg(t[v * 2], t[v * 2 + 1]);
}
void upd(int v, int l, int r, int x) {
psh(v);
if (t[v].mn > h) {
t[v].Dx = h;
psh(v);
return;
}
if (t[v].mx < 0) {
t[v].Dx = 0;
psh(v);
return;
}
if (l == r || (t[v].mn >= 0 && t[v].mx <= h)) {
return;
}
int md = (l + r) >> 1;
upd(v * 2, l, md, 0);
upd(v * 2 + 1, md + 1, r, 0);
t[v].mrg(t[v * 2], t[v * 2 + 1]);
}
void upd(int l, int r, int val) {
upd(1, 0, n - 1, l, r, val);
upd(1, 0, n - 1, 0);
}
int get(int v, int l, int r, int ps) {
psh(v);
if (l == r) {
return t[v].mx;
} else {
int md = (l + r) >> 1;
if (ps <= md) {
return get(v * 2, l, md, ps);
}
return get(v * 2 + 1, md + 1, r, ps);
}
}
int get(int x) {
return get(1, 0, n - 1, x);
}
} stb;
struct st_min {
vector <ll> t;
int n;
st_min() {}
void build(int v, int l, int r, vector <ll> &a) {
if (l == r) {
t[v] = abs(a[l]);
return;
} else {
int md = (l + r) >> 1;
build(v * 2, l, md, a);
build(v * 2 + 1, md + 1, r, a);
t[v] = min(t[v * 2], t[v * 2 + 1]);
}
}
void init(vector <ll> &a) {
n = sz(a);
t.resize(8 * n);
build(1, 0, n - 1, a);
}
void upd(int v, int l, int r, int ps, ll val) {
if (l == r) {
t[v] = val;
return;
} else {
int md = (l + r) >> 1;
if (ps <= md) {
upd(v * 2, l, md, ps, val);
} else {
upd(v * 2 + 1, md + 1, r, ps, val);
}
t[v] = min(t[v * 2], t[v * 2 + 1]);
}
}
int get(int v, int l, int r, ll c) {
if (t[v] >= c) {
return -1;
}
if (l == r) {
return l;
}
int md = (l + r) >> 1;
int cur = get(v * 2, l, md, c);
if (cur == -1) {
return get(v * 2 + 1, md + 1, r, c);
}
return cur;
}
void upd(int ps, ll val) {
upd(1, 0, n - 1, ps, val);
}
int get(ll c) {
return get(1, 0, n - 1, c);
}
};
vector <int> solve_st_beats(vector <int> &c, vector <int> &l, vector <int> &r, vector <int> &v) {
int n = sz(c), q = sz(l);
stb.init(n, c[0]);
for (int i = 0; i < q; i++) {
stb.upd(l[i], r[i], v[i]);
}
vector <int> a(n);
for (int i = 0; i < n; i++) {
a[i] = stb.get(i);
}
return a;
}
vector <int> solve_offline(vector <int> &c, vector <int> &l, vector <int> &r, vector <int> &v) {
vector <ll> p = {v[0]};
int q = sz(l), n = sz(c);
vector <int> nxt(q, 0);
set <pair <int, ll> > se;
auto sg = [&](ll x) {
if (x < 0) {
return -1;
}
return 1;
};
for (int i = 1; i < q; i++) {
if (sg(p.back()) == sg(v[i])) {
p.back() += v[i];
} else {
p.pb(v[i]);
}
}
if (p[0] < 0) {
p.erase(p.begin());
}
q = sz(p);
for (int i = 0; i < q; i++) {
nxt[i] = i + 1;
se.insert({i, p[i]});
}
vector <int> ind(n, 0);
iota(all(ind), 0);
sort(all(ind), [&](int i, int j) {return (c[i] < c[j]);});
st_min tM;
tM.init(p);
vector <int> ans(n, 0);
for (auto i : ind) {
ll x = c[i];
// cerr << x << el;
int j = tM.get(x);
while (j != -1) {
ll new_val = p[j], shift = 0;
if (new_val < 0) {
shift = x;
}
int was = j;
se.erase({j, p[j]});
vector <int> pos;
while (nxt[j] < q && shift + new_val >= 0 && shift + new_val <= x) {
j = nxt[j];
pos.pb(j);
se.erase({j, p[j]});
new_val += p[j];
p[j] = 0;
}
for (auto k : pos) {
nxt[k] = nxt[j];
tM.upd(k, 2e18);
}
nxt[was] = nxt[j];
auto it = se.lower_bound(make_pair(j, 0));
if (it != se.begin()) {
--it;
if (sg(it -> S) == sg(new_val)) {
new_val += it -> S;
nxt[it -> F] = nxt[j];
p[was] = 0;
p[it -> F] = new_val;
tM.upd(was, 2e18);
tM.upd(it -> F, abs(new_val));
was = it -> F;
se.erase(it);
se.insert({was, new_val});
} else {
p[was] = new_val;
se.insert({was, new_val});
tM.upd(was, abs(new_val));
}
} else {
p[was] = new_val;
se.insert({was, new_val});
tM.upd(was, abs(new_val));
}
while (sz(se) && se.begin() -> S < 0) {
int w = se.begin() -> F;
p[w] = 0;
tM.upd(w, 2e18);
se.erase(se.begin());
}
if (nxt[j] == q) {
break;
}
j = tM.get(x);
}
if (!sz(se)) {
ans[i] = 0;
continue;
}
ll val = se.rbegin() -> S;
if (val < 0) {
if (se.rbegin() -> F) {
ans[i] = max(0ll, x + val);
} else {
ans[i] = 0;
}
} else {
ans[i] = min(x, val);
}
// for (int j = 0; j < q; j++) {
// cerr << p[j] << " ";
// }
// cerr << el;
}
return ans;
}
vector <int> distribute_candies(vector <int> c, vector <int> l, vector <int> r, vector <int> v) {
int n = sz(c), q = sz(l);
bool is_brute = 1;
if (is_brute && n <= 2000 && q <= 2000) {
vector <int> a(n, 0);
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;
} else {
bool g = 1;
for (int i = 0; i < q; i++) {
g &= (v[i] > 0);
}
if (g) {
vector <ll> pf(n, 0);
vector <int> a(n, 0);
for (int i = 0; i < q; i++) {
pf[l[i]] += v[i];
if (r[i] + 1 < n) {
pf[r[i] + 1] -= v[i];
}
}
for (int i = 1; i < n; i++) {
pf[i] += pf[i - 1];
}
for (int i = 0; i < n; i++) {
a[i] = min(max(0ll, pf[i]), (ll)c[i]);
}
return a;
} else {
bool eq_c = 1;
for (int i = 1; i < n; i++) {
eq_c &= (c[i] == c[0]);
}
if (eq_c) {
return solve_st_beats(c, l, r, v);
}
return solve_offline(c, l, r, v);
}
}
}
/*
10
29 75 94 69 8 86 16 97 50 77
10
0 9 38
0 9 -21
0 9 -6
0 9 -3
0 9 2
0 9 -24
0 9 -9
0 9 -32
0 9 -41
0 9 46
29 46 46 46 8 46 16 0 46 46
29 46 46 46 8 46 16 46 46 46
10
99 5 25 85 6 20 41 83 87 87
10
0 9 -17
0 9 21
0 9 31
0 9 -25
0 9 -18
0 9 50
0 9 -41
0 9 -43
0 9 14
0 9 -25
63 0 14 49 0 9 30 47 51 51
0 0 0 0 0 0 0 0 0 0
10
75 24 49 95 80 40 28 41 85 57
10
0 9 -48
0 9 -15
0 9 20
0 9 44
0 9 43
0 9 39
0 9 -49
0 9 -16
0 9 -36
0 9 45
45 24 45 45 45 40 28 41 45 45
10
82 85 7 36 68 4 90 93 32 14
10
0 9 16
0 9 -6
0 9 47
0 9 3
0 9 -36
0 9 6
0 9 41
0 9 -27
0 9 -24
0 9 -12
8 8 0 0 5 0 8 8 0 0
10
55 26 63 57 58 10 89 91 45 72
10
0 9 90
0 9 -37
0 9 87
0 9 35
0 9 26
0 9 -52
0 9 -30
0 9 77
0 9 -87
0 9 45
45 26 45 45 45 10 45 45 45 45
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
3 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
8888 KB |
Output is correct |
| 2 |
Correct |
91 ms |
8812 KB |
Output is correct |
| 3 |
Correct |
97 ms |
8808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
131 ms |
5452 KB |
Output is correct |
| 3 |
Correct |
90 ms |
53972 KB |
Output is correct |
| 4 |
Correct |
357 ms |
57448 KB |
Output is correct |
| 5 |
Correct |
445 ms |
57448 KB |
Output is correct |
| 6 |
Correct |
545 ms |
57548 KB |
Output is correct |
| 7 |
Correct |
458 ms |
57448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
153 ms |
19144 KB |
Output is correct |
| 4 |
Correct |
74 ms |
4736 KB |
Output is correct |
| 5 |
Correct |
237 ms |
25664 KB |
Output is correct |
| 6 |
Correct |
270 ms |
26316 KB |
Output is correct |
| 7 |
Correct |
232 ms |
26960 KB |
Output is correct |
| 8 |
Correct |
239 ms |
25784 KB |
Output is correct |
| 9 |
Correct |
97 ms |
13800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
3 ms |
340 KB |
Output is correct |
| 6 |
Correct |
99 ms |
8888 KB |
Output is correct |
| 7 |
Correct |
91 ms |
8812 KB |
Output is correct |
| 8 |
Correct |
97 ms |
8808 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
131 ms |
5452 KB |
Output is correct |
| 11 |
Correct |
90 ms |
53972 KB |
Output is correct |
| 12 |
Correct |
357 ms |
57448 KB |
Output is correct |
| 13 |
Correct |
445 ms |
57448 KB |
Output is correct |
| 14 |
Correct |
545 ms |
57548 KB |
Output is correct |
| 15 |
Correct |
458 ms |
57448 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
153 ms |
19144 KB |
Output is correct |
| 19 |
Correct |
74 ms |
4736 KB |
Output is correct |
| 20 |
Correct |
237 ms |
25664 KB |
Output is correct |
| 21 |
Correct |
270 ms |
26316 KB |
Output is correct |
| 22 |
Correct |
232 ms |
26960 KB |
Output is correct |
| 23 |
Correct |
239 ms |
25784 KB |
Output is correct |
| 24 |
Correct |
97 ms |
13800 KB |
Output is correct |
| 25 |
Correct |
1 ms |
212 KB |
Output is correct |
| 26 |
Incorrect |
86 ms |
4780 KB |
Output isn't correct |
| 27 |
Halted |
0 ms |
0 KB |
- |
