#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())
const int maxn = 2e5 + 5, bsize = 600;
struct Node {
long pref, suff, sum, v;
Node operator+(const Node& n) const {
return {max(pref, sum + n.pref), max(n.suff, suff + n.sum), sum + n.sum,
max({v, n.v, suff + n.pref})};
}
static Node from(int x) {
return {x, x, x, x};
}
};
struct DS {
int n, t;
vector<int> arr, nx, changed;
vector<Node> v;
DS(int n)
: n(n),
t(0),
arr(n),
nx(n, n + 1),
changed(n / bsize + 3),
v(4 * n, Node::from(0)) {}
void update(int o, int l, int r, int ind, int x) {
if (l == r) {
v[o] = Node::from(x);
} else {
int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
if (ind <= mid) {
update(lc, l, mid, ind, x);
} else {
update(rc, mid + 1, r, ind, x);
}
v[o] = v[lc] + v[rc];
}
}
void set(int ind, int x) {
arr[ind] = x;
changed[ind / bsize] = t;
update(1, 0, n - 1, ind, x);
}
Node query(int o, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return v[o];
} else {
int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
if (ql <= mid) {
if (mid < qr) {
return query(lc, l, mid, ql, qr) +
query(rc, mid + 1, r, ql, qr);
}
return query(lc, l, mid, ql, qr);
} else {
return query(rc, mid + 1, r, ql, qr);
}
}
}
Node query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
long sum(int l, int r) {
if (l > r) {
return 0;
}
return query(l, r).sum;
}
int bsearch1(int x) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) / 2;
if (query(mid, n - 1).v < x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
int nxt(int ql) {
int l = ql - 1, r = n - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (query(ql, mid).pref <= 0) {
l = mid;
} else {
r = mid - 1;
}
}
return l + 2;
}
void build() {
static long psum[maxn];
for (int i = 0; i <= n / bsize; i++) {
if (changed[i] == t) {
int l = i * bsize, r = min(n, l + bsize);
if (l >= r) {
break;
}
psum[l] = 0;
for (int j = l; j < r; j++) {
psum[j + 1] = arr[j] + psum[j];
}
vector<pair<long, int>> s;
for (int j = r; j >= l; j--) {
while (sz(s) && s.back().first <= psum[j]) {
s.pop_back();
}
if (j < r) {
if (sz(s)) {
nx[j] = s.back().second;
} else {
nx[j] = j;
}
}
s.emplace_back(psum[j], j);
}
}
}
t++;
}
int nxt2(int x) {
while (true) {
if (x == n) {
return x;
}
int y = nx[x];
if (y == n) {
return y;
}
x = y;
y = nxt(x);
if (y > n) {
return x;
}
x = y;
}
}
};
vector<int> distribute_candies(vector<int> arr,
vector<int> ql,
vector<int> qr,
vector<int> qv) {
int n = sz(arr), q = sz(ql);
vector<pair<int, int>> upds[n + 1];
for (int i = 0; i < q; i++) {
upds[ql[i]].emplace_back(i, qv[i]);
upds[qr[i] + 1].emplace_back(i, 0);
}
DS pos(q), neg(q);
vector<int> ans(n);
for (int i = 0; i < n; i++) {
for (auto& [ind, x] : upds[i]) {
pos.set(ind, x);
neg.set(ind, -x);
}
pos.build();
neg.build();
int posi = pos.bsearch1(arr[i]), negi = neg.bsearch1(arr[i]);
dbg(posi, negi);
if (posi == negi) {
assert(!posi);
}
if (posi > negi) {
ans[i] = arr[i] + pos.sum(pos.nxt2(posi), q - 1);
} else {
ans[i] = pos.sum(neg.nxt2(negi), q - 1);
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
964 KB |
Output is correct |
| 4 |
Correct |
6 ms |
980 KB |
Output is correct |
| 5 |
Correct |
37 ms |
980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5022 ms |
74612 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
3480 ms |
67360 KB |
Output is correct |
| 3 |
Correct |
1050 ms |
10800 KB |
Output is correct |
| 4 |
Execution timed out |
5014 ms |
79808 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
384 ms |
65520 KB |
Output is correct |
| 4 |
Correct |
2051 ms |
9192 KB |
Output is correct |
| 5 |
Execution timed out |
5038 ms |
73484 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
964 KB |
Output is correct |
| 4 |
Correct |
6 ms |
980 KB |
Output is correct |
| 5 |
Correct |
37 ms |
980 KB |
Output is correct |
| 6 |
Execution timed out |
5022 ms |
74612 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
