#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
int n, smax[800000], smin[800000], scur[800000], scap[800000], inf = 2000000001;
vector<int> s;
int mincap(int id, int l, int r, int ll, int rr, vector<int> c) {
if (l > rr || r < ll) return l;
if (l <= ll && r >= rr) return scap[id];
int mid = (ll + rr) / 2, x1 = mincap(id * 2, l, r, ll, mid, c), x2 = mincap(id * 2 + 1, l, r, mid + 1, rr, c);
if (c[x1] < c[x2]) return x1;
return x2;
}
void updcap(int id, int lr, int ll, int rr, vector<int> c) {
if (ll == rr) {
scap[id] = lr;
return;
}
int mid = (ll + rr) / 2;
if (lr <= mid) {
updcap(id * 2, lr, ll, mid, c);
} else {
updcap(id * 2 + 1, lr, mid + 1, rr, c);
}
if (c[scap[id * 2]] < c[scap[id * 2 + 1]]) {
scap[id] = scap[id * 2];
} else {
scap[id] = scap[id * 2 + 1];
}
return;
}
pair<int, pair<int, int>> eat(int id, int lr, int ll, int rr, vector<int> c) {
pair<int, pair<int, int>> px;
if (ll == rr) {
px = make_pair(scur[id], make_pair(smax[id], smin[id]));
return px;
}
int mid = (ll + rr) / 2;
if (lr <= mid) {
px = eat(id * 2, lr, ll, mid, c);
} else {
px = eat(id * 2 + 1, lr, mid + 1, rr, c);
}
if (px.first == inf) return px;
int dif = max(smax[id] + px.first, px.second.first) - min(smin[id] + px.first, px.second.second);
if (dif >= c[lr]) {
if (smax[id] + px.first > px.second.first) {
s[lr] = - px.second.second;
} else {
s[lr] = c[lr] - px.second.first;
}
c[lr] = inf;
updcap(1, lr, 0, n - 1, c);
px.first = inf;
} else {
px.second.first = max(smax[id] + px.first, px.second.first);
px.second.second = min(smin[id] + px.first, px.second.second);
px.first += scur[id];
}
return px;
}
void puttag(int id, int ma, int mi, int cu, vector<int> c) {
if (c[scap[id]] == inf) return;
int dif = max(ma + scur[id], smax[id]) - min(mi + scur[id], smin[id]);
while (dif >= c[scap[id]]) {
pair<int, pair<int, int>> px = eat(1, scap[id], 0, n - 1, c);
if (px.first != inf) {
if (ma + px.first > px.second.first) {
s[scap[id]] = - px.second.second;
} else {
s[scap[id]] = c[scap[id]] - px.second.first;
}
c[scap[id]] = inf;
updcap(1, scap[id], 0, n - 1, c);
px.first = inf;
}
}
smax[id] = max(ma + scur[id], smax[id]);
smin[id] = min(mi + scur[id], smin[id]);
scur[id] += cu;
return;
}
void push(int id, vector<int> c) {
int ma = smax[id], mi = smin[id], cu = scur[id];
smax[id] = 0, smin[id] = 0, scur[id] = 0;
puttag(id * 2, ma, mi, cu, c);
puttag(id * 2 + 1, ma, mi, cu, c);
return;
}
void modify(int id, int val, int l, int r, int ll, int rr, vector<int> c) {
if (l > rr || r < ll) return;
if (l <= ll && r >= rr) {
puttag(id, max(0, -val), min(0, -val), -val, c);
return;
}
push(id, c);
int mid = (ll + rr) / 2;
modify(id * 2, val, l, r, ll, mid, c);
modify(id * 2 + 1, val, l, r, mid + 1, rr, c);
return;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
n = c.size();
s.resize(n);
for (int i = 0; i < n; i++) {
updcap(1, i, 0, n - 1, c);
}
for (int i = l.size() - 1; i >= 0; i--) {
modify(1, v[i], l[i], r[i], 0, n - 1, c);
}
for (int i = 0; i < n; i++) {
if (c[i] != inf) {
pair<int, pair<int, int>> px = eat(1, i, 0, n - 1, c);
if (px.first != inf) s[i] = - px.second.second;
}
}
return s;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5036 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5003 ms |
27748 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5036 ms |
324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5050 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5036 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
