#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define int long long
#define sl i + 1
#define sr i + (sm - ss + 1) * 2
#define sm (ss + se) / 2
#define block 350
int pend[400005], tree[400005], pend2[400005];
int pre[200005];
void push(int i, int ss, int se) {
// assert(!(pend[i] and pend2[i]));
if (pend2[i] == 1) {
tree[i] = 0;
if (ss != se) {
pend2[sl] = 1;
pend2[sr] = 1;
pend[sl] = 0;
pend[sr] = 0;
}
pend2[i] = 0;
}
if (pend2[i] == 2) {
tree[i] = pre[se] - (ss ? pre[ss - 1] : 0);
if (ss != se) {
pend2[sl] = 2;
pend2[sr] = 2;
pend[sl] = 0;
pend[sr] = 0;
}
pend2[i] = 0;
}
if (pend[i]) {
tree[i] += pend[i];
if (ss != se) {
pend[sl] += pend[i];
pend[sr] += pend[i];
}
pend[i] = 0;
}
}
void upd(int l, int r, int val, int ss = 0, int se = 200000, int i = 0) {
push(i, ss, se);
if (ss > se or l > se or r < ss) return;
if (ss >= l and se <= r) {
pend[i] += val;
// cout << i << endl;
push(i, ss, se);
return;
}
upd(l, r, val, ss, sm, sl);
upd(l, r, val, sm + 1, se, sr);
tree[i] = max(tree[sl], tree[sr]);
}
void forc(int l, int r, int val, int ss = 0, int se = 200000, int i = 0) {
push(i, ss, se);
if (ss > se or l > se or r < ss) return;
if (ss >= l and se <= r) {
pend2[i] = val;
push(i, ss, se);
return;
}
forc(l, r, val, ss, sm, sl);
forc(l, r, val, sm + 1, se, sr);
tree[i] = max(tree[sl], tree[sr]);
}
int get(int l, int r, int ss = 0, int se = 200000, int i = 0) {
push(i, ss, se);
if (ss > se or ss > r or se < l) return 0;
if (ss >= l and se <= r) return tree[i];
return max(get(l, r, ss, sm, sl), get(l, r, sm + 1, se, sr));
}
std::vector<signed> distribute_candies(std::vector<signed> c, std::vector<signed> l,
std::vector<signed> r, std::vector<signed> v) {
int n = c.size();
int q = l.size();
vector<pair<int, int>> all;
for (int i = 0; i < n; ++i) all.push_back({c[i], i});
sort(all.begin(), all.end());
pre[0] = all[0].first;
for (int i = 1; i < n; ++i) {
pre[i] = pre[i - 1] + all[i].first;
}
// for (int i = 0; i < n; ++i) {
// cout << pre[i] << ' ';
// }
// cout << endl;
for (int i = 0; i < q; ++i) {
int x = v[i];
if (x > 0) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (get(0, mid) + x < all[mid].first) hi = mid - 1;
else lo = mid + 1;
}
// hi = -1;
if (hi != -1) {
forc(0, hi, 2);
}
// cout << hi << endl;
upd(hi + 1, n - 1, x);
// cout << get(0, n - 1) << endl;
} else {
x *= -1;
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (get(0, mid) > x) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
// cout << hi << endl;
// hi = -1;
if (hi != -1) {
forc(0, hi, 1);
}
upd(hi + 1, n - 1, -x);
}
}
std::vector<signed> s(n);
for (int i = 0; i < n; ++i) {
s[all[i].second] = get(i, i);
}
return s;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1094 ms |
26280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
