#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5;
//const int N = 10;
const ll inf = 2e18;
struct ST {
ll t[4 * N], mn[4 * N], mx[4 * N];
ST(){
fill(t, t + 4 * N, 0);
fill(mn, mn + 4 * N, 0);
fill(mx, mx + 4 * N, 0);
}
inline void push(int v) {
t[2 * v + 1] += t[v], mn[2 * v + 1] += t[v], mx[2 * v + 1] += t[v];
t[2 * v + 2] += t[v], mn[2 * v + 2] += t[v], mx[2 * v + 2] += t[v];
t[v] = 0;
}
inline void upd(int v) {
mn[v] = min(mn[2 * v + 1], mn[2 * v + 2]), mx[v] = max(mx[2 * v + 1], mx[2 * v + 2]);
}
void add(int v, int tl, int tr, int l, int r, ll d) {
if (tl >= r || tr <= l)
return;
if (tl >= l && tr <= r) {
t[v] += d, mn[v] += d, mx[v] += d;
return;
}
push(v);
int m = (tl + tr) / 2;
add(2 * v + 1, tl, m, l, r, d);
add(2 * v + 2, m, tr, l, r, d);
upd(v);
}
ll get_min(int v, int tl, int tr, int l, int r) {
if (tl >= r || tr <= l)
return inf;
if (tl >= l && tr <= r)
return mn[v];
push(v);
int m = (tl + tr) / 2;
ll ans = min(get_min(2 * v + 1, tl, m, l, r), get_min(2 * v + 2, m, tr, l, r));
upd(v);
return ans;
}
ll get_max(int v, int tl, int tr, int l, int r) {
if (tl >= r || tr <= l)
return -inf;
if (tl >= l && tr <= r)
return mx[v];
push(v);
int m = (tl + tr) / 2;
ll ans = max(get_max(2 * v + 1, tl, m, l, r), get_max(2 * v + 2, m, tr, l, r));
upd(v);
return ans;
}
ll get_val(int v, int tl, int tr, int i) {
if (i < tl || i >= tr)
return 0;
if (tl + 1 == tr)
return t[v];
push(v);
int m = (tl + tr) / 2;
ll ans;
if (i < m)
ans = get_val(2 * v + 1, tl, m, i);
else
ans = get_val(2 * v + 2, m, tr, i);
upd(v);
return ans;
}
};
vector<pair<int, int>> ev[2 * N];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int q = l.size(), n = c.size();
for (int i = 0; i < q; i++) {
ev[l[i]].push_back({i, v[i]});
ev[r[i]+1].push_back({i, -v[i]});
}
ST st;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
for (auto p : ev[i])
st.add(0, 0, q, p.first, q, p.second);
int last_over = -1;
if (st.get_max(0, 0, q, 0, q) > c[i]) {
int l = 0, r = q;
while (r - l > 1) {
int mid = (r + l) / 2;
if (st.get_max(0, 0, q, mid, q) > c[i])
l = mid;
else
r = mid;
}
last_over = l;
}
int last_under = -1;
if (st.get_min(0, 0, q, 0, q) < 0) {
int l = 0, r = q;
while (r - l > 1) {
int mid = (r + l) / 2;
if (st.get_min(0, 0, q, mid, q) < 0)
l = mid;
else
r = mid;
}
last_under = l;
}
if (last_over > last_under) {
ans[i] = 1ll * c[i] + st.get_val(0, 0, q, q - 1) - st.get_val(0, 0, q, last_over);
} else {
ans[i] = st.get_val(0, 0, q, q - 1) - st.get_val(0, 0, q, last_under);
}
ans[i] = min(ans[i], c[i]);
ans[i] = max(ans[i], 0);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
28372 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
28476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
975 ms |
42564 KB |
Output is correct |
| 2 |
Correct |
940 ms |
46540 KB |
Output is correct |
| 3 |
Correct |
919 ms |
46444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
28372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
28372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
28372 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
28476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
