#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];
p[was] = new_val;
se.insert({was, new_val});
tM.upd(was, abs(new_val));
if (nxt[j] == q) {
break;
}
j = tM.get(x);
}
ll val = se.rbegin() -> S;
if (val < 0) {
ans[i] = max(0ll, x + val);
} 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);
if (0 && 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
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 |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
13656 KB |
Output is correct |
| 2 |
Correct |
101 ms |
12884 KB |
Output is correct |
| 3 |
Correct |
120 ms |
12764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
137 ms |
8528 KB |
Output is correct |
| 3 |
Correct |
116 ms |
56092 KB |
Output is correct |
| 4 |
Correct |
365 ms |
63372 KB |
Output is correct |
| 5 |
Correct |
483 ms |
63748 KB |
Output is correct |
| 6 |
Correct |
583 ms |
64140 KB |
Output is correct |
| 7 |
Correct |
436 ms |
63480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
