#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int mxN = 2e5 + 1;
struct info {
int net; // net change
int mini, maxi;
info(): net(0), mini(1e18), maxi(-1e18) {};
info(int val): net(val), mini(val), maxi(val) {};
};
info merge(info &lhs, info &rhs) {
info res;
res.net = lhs.net + rhs.net;
res.mini = min(lhs.mini, min(0LL, lhs.net) + rhs.mini);
res.maxi = max(lhs.maxi, max(0LL, lhs.net) + rhs.maxi);
return res;
}
info EMPTY = info();
info ZERO = info(0);
info seg[4 * mxN];
int lazy[4 * mxN];
int n, q;
void build(int l = 0, int r = q, int idx = 1) {
if (l == r) {
if (l == 0) seg[idx] = info(0);
else seg[idx] = info();
return;
}
int mid = (l + r) >> 1;
build(l, mid, (idx << 1));
build(mid + 1, r, (idx << 1) | 1);
seg[idx] = merge(seg[(idx << 1)], seg[(idx << 1) | 1]);
}
void update(int pos, int val, int l = 0, int r = q, int idx = 1) {
if (l == r) {
if (val == 0) seg[idx] = info();
else seg[idx] = info(val);
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(pos, val, l, mid, (idx << 1));
else update(pos, val, mid + 1, r, (idx << 1) | 1);
seg[idx] = merge(seg[(idx << 1)], seg[(idx << 1) | 1]);
// cerr << l << ' ' << r << ", " << idx << ": ";
// cerr << seg[idx].net << ' ' << seg[idx].mini << ' ' << seg[idx].maxi << endl;
}
// range find net min/max
pii query1(int tl, int tr, int l = 0, int r = q, int idx = 1, int buff = 0) {
if (tl > tr) return {0, 0};
if (tl <= l && r <= tr) return {buff + seg[idx].mini, buff + seg[idx].maxi};
int mid = (l + r) >> 1;
pii res = {1e18, -1e18}, ret;
if (tl <= mid) {
ret = query1(tl, tr, l, mid, (idx << 1), buff);
res.ff = min(res.ff, ret.ff); res.ss = max(res.ss, ret.ss);
}
if (tr > mid) {
ret = query1(tl, tr, mid + 1, r, (idx << 1) | 1, buff + seg[(idx << 1)].net);
res.ff = min(res.ff, ret.ff); res.ss = max(res.ss, ret.ss);
}
return res;
}
// find largest pos s.t. max(upd[pos..n]) - min(upd[pos..n]) > (tar = c[i])
int query2(int tar, pii range, int l = 0, int r = q, int idx = 1, int buff = 0) {
// cerr << l << ' ' << r << ", " << idx << ": ";
// cerr << seg[idx].net << ' ' << seg[idx].mini << ' ' << seg[idx].maxi << " | ";
// cerr << range.ff << ' ' << range.ss << endl;
if (max(range.ss, buff + seg[idx].maxi) - min(range.ff, buff + seg[idx].mini) <= tar) {
return -1;
}
if (l == r) return l;
int mid = (l + r) >> 1;
int rmini = buff + seg[(idx << 1)].net + seg[(idx << 1) | 1].mini;
int rmaxi = buff + seg[(idx << 1)].net + seg[(idx << 1) | 1].maxi;
if (max(range.ss, rmaxi) - min(range.ff, rmini) <= tar) {
range.ss = max(range.ss, rmaxi);
range.ff = min(range.ff, rmini);
return query2(tar, range, l, mid, (idx << 1), buff);
} else {
return query2(tar, range, mid + 1, r, (idx << 1) | 1, buff + seg[(idx << 1)].net);
}
return -1;
}
vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l,
vector<int32_t> r, vector<int32_t> v) {
n = c.size(); q = v.size();
build();
vector<pii> upd[n + 2];
for (int i = 0; i < q; i++) {
l[i]++; r[i]++;
upd[l[i]].pb({i + 1, v[i]});
upd[r[i] + 1].pb({i + 1, 0});
}
vector<int32_t> ans;
for (int i = 1; i <= n; i++) {
for (pii &cur : upd[i]) {
update(cur.ff, cur.ss);
}
int tot = seg[1].net;
int crit = query2(c[i - 1], {tot, tot});
pii range;
if (crit == -1) {
range = query1(1, q);
ans.pb(tot - range.ff);
continue;
}
int prev = query1(crit, crit).ff;
range = query1(crit + 1, q);
// cerr << i << ": " << tot << ' ' << crit << ' ' << prev << " | ";
// cerr << range.ff << ' ' << range.ss << endl;
if (prev < range.ff) {
range.ff = range.ss - c[i - 1];
ans.pb(tot - range.ff);
} else {
range.ss = range.ff + c[i - 1];
ans.pb(c[i - 1] - (range.ss - tot));
}
}
return ans;
}
#undef int
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
19072 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
19028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
367 ms |
46460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
19072 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
19028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
