#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];
}
for (auto k : pos) {
nxt[k] = j;
tM.upd(k, 2e18);
}
if (was != j) {
nxt[was] = 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);
}
}
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 (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
88 49 94 26 31 20 35 61 24 33
10
0 9 79
0 9 83
0 9 26
0 9 11
0 9 63
0 9 13
0 9 9
0 9 94
0 9 50
0 9 84
88 49 94 26 31 20 35 61 24 33
10
94 64 84 2 39 19 82 24 28 0
10
0 9 19
0 9 90
0 9 80
0 9 5
0 9 31
0 9 95
0 9 53
0 9 20
0 9 84
0 9 31
94 64 84 2 39 19 82 24 28 0
*/
| # |
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 |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
5 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
8800 KB |
Output is correct |
| 2 |
Correct |
103 ms |
8888 KB |
Output is correct |
| 3 |
Correct |
97 ms |
8800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
125 ms |
5520 KB |
Output is correct |
| 3 |
Correct |
91 ms |
53888 KB |
Output is correct |
| 4 |
Correct |
350 ms |
57548 KB |
Output is correct |
| 5 |
Correct |
445 ms |
57440 KB |
Output is correct |
| 6 |
Correct |
503 ms |
57440 KB |
Output is correct |
| 7 |
Correct |
463 ms |
57464 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 |
Execution timed out |
5079 ms |
19072 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
5 ms |
340 KB |
Output is correct |
| 6 |
Correct |
100 ms |
8800 KB |
Output is correct |
| 7 |
Correct |
103 ms |
8888 KB |
Output is correct |
| 8 |
Correct |
97 ms |
8800 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
125 ms |
5520 KB |
Output is correct |
| 11 |
Correct |
91 ms |
53888 KB |
Output is correct |
| 12 |
Correct |
350 ms |
57548 KB |
Output is correct |
| 13 |
Correct |
445 ms |
57440 KB |
Output is correct |
| 14 |
Correct |
503 ms |
57440 KB |
Output is correct |
| 15 |
Correct |
463 ms |
57464 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Execution timed out |
5079 ms |
19072 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
