#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
// editorial
struct segtree {
using T = pair<long long, long long>;
using F = long long;
T e() {
return make_pair((long long) 1e18, (long long) -1e18);
}
F id() {
return 0;
}
T op(T a, T b) {
a.first = min(a.first, b.first);
a.second = max(a.second, b.second);
return a;
}
T mapping(F f, T x) {
x.first += f;
x.second += f;
return x;
}
F composition(F f, F g) {
return f + g;
}
int n;
int size;
int log_size;
vector<T> node;
vector<F> lazy;
segtree() : segtree(0) {}
segtree(int _n) {
build(vector<T>(_n, e()));
}
segtree(const vector<T>& v) {
build(v);
}
void build(const vector<T>& v) {
n = (int) v.size();
if (n <= 1) {
log_size = 0;
} else {
log_size = 32 - __builtin_clz(n - 1);
}
size = 1 << log_size;
node.resize(2 * size, e());
lazy.resize(size, id());
for (int i = 0; i < n; i++) {
node[i + size] = v[i];
}
for (int i = size - 1; i > 0; i--) {
pull(i);
}
}
void push(int x) {
node[2 * x] = mapping(lazy[x], node[2 * x]);
node[2 * x + 1] = mapping(lazy[x], node[2 * x + 1]);
if (2 * x < size) {
lazy[2 * x] = composition(lazy[x], lazy[2 * x]);
lazy[2 * x + 1] = composition(lazy[x], lazy[2 * x + 1]);
}
lazy[x] = id();
}
void pull(int x) {
node[x] = op(node[2 * x], node[2 * x + 1]);
}
void set(int p, T v) {
assert(0 <= p && p < n);
p += size;
for (int i = log_size; i >= 1; i--) {
push(p >> i);
}
node[p] = v;
for (int i = 1; i <= log_size; i++) {
pull(p >> i);
}
}
T get(int p) {
assert(0 <= p && p < n);
p += size;
for (int i = log_size; i >= 1; i--) {
push(p >> i);
}
return node[p];
}
T get(int l, int r) {
assert(0 <= l && l <= r && r <= n);
l += size;
r += size;
for (int i = log_size; i >= 1; i--) {
if (((l >> i) << i) != l) {
push(l >> i);
}
if (((r >> i) << i) != r) {
push((r - 1) >> i);
}
}
T vl = e();
T vr = e();
while (l < r) {
if (l & 1) {
vl = op(vl, node[l++]);
}
if (r & 1) {
vr = op(node[--r], vr);
}
l >>= 1;
r >>= 1;
}
return op(vl, vr);
}
void apply(int p, F f) {
assert(0 <= p && p < n);
p += size;
for (int i = log_size; i >= 1; i--) {
push(p >> i);
}
node[p] = mapping(f, node[p]);
for (int i = 1; i <= log_size; i++) {
pull(p >> i);
}
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= n);
l += size;
r += size;
for (int i = log_size; i >= 1; i--) {
if (((l >> i) << i) != l) {
push(l >> i);
}
if (((r >> i) << i) != r) {
push((r - 1) >> i);
}
}
int ll = l;
int rr = r;
while (l < r) {
if (l & 1) {
node[l] = mapping(f, node[l]);
if (l < size) {
lazy[l] = composition(f, lazy[l]);
}
l++;
}
if (r & 1) {
r--;
node[r] = mapping(f, node[r]);
if (l < size) {
lazy[r] = composition(f, lazy[r]);
}
}
l >>= 1;
r >>= 1;
}
l = ll;
r = rr;
for (int i = 1; i <= log_size; i++) {
if (((l >> i) << i) != l) {
pull(l >> i);
}
if (((r >> i) << i) != r) {
pull((r - 1) >> i);
}
}
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = (int) c.size();
int q = (int) v.size();
segtree seg(vector<pair<long long, long long>>(q + 1, make_pair(0LL, 0LL)));
vector<vector<int>> events(n + 1);
for (int i = 0; i < q; i++) {
events[l[i]].emplace_back(i);
events[r[i] + 1].emplace_back(i);
}
vector<int> res(n);
for (int i = 0; i < n; i++) {
for (int j : events[i]) {
if (l[j] == i) {
seg.apply(j + 1, q + 1, v[j]);
} else {
seg.apply(j + 1, q + 1, -v[j]);
}
}
auto last = seg.get(q).first;
int low = -1;
int high = q;
while (high - low > 1) {
int mid = (high + low) >> 1;
auto p = seg.get(mid, q);
if (p.second - p.first <= c[i]) {
high = mid;
} else {
low = mid;
}
}
debug(low, seg.node[1]);
if (low == -1) {
res[i] = (int) (last - seg.node[1].first);
} else {
auto p = seg.get(low, q);
auto now = seg.get(low).first;
if (p.second == now) {
res[i] = min(c[i], (int) (last - p.first));
} else if (p.first == now) {
res[i] = max(0, (int) (c[i] + last - p.second));
} else {
assert(false);
}
}
}
return res;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
debug(distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11}));
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1104 ms |
32756 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 |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
