#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5;
//const int N = 1000;
const ll inf = 2e18;
struct ST {
ll t[4 * N], mn[4 * N], mx[4 * N];
ll q;
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;
}
ll get_min(int left) {
return get_min(0, 0, q, left+1, q);
}
ll get_max(int left) {
return get_max(0, 0, q, left+1, q);
}
ll get_val(int ind) {
return get_val(0, 0, q, ind+1);
}
ll get_range(int left) {
return get_max(left) - get_min(left);
}
void add(int left, int right, ll d) {
add(0, 0, q, left + 1, right + 1, d);
}
};
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;
st.q = q+1;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
for (auto p : ev[i])
st.add(p.first, q, p.second);
ll range = st.get_range(-1);
if (range <= c[i]) {
ans[i] = st.get_val(q) - st.get_min(-1);
continue;
}
int l = -1, r = q;
while (r - l > 1) {
int mid = (r + l) / 2;
if (st.get_range(mid) > c[i])
l = mid;
else
r = mid;
}
ll left_val = st.get_val(l), last_val = st.get_val(q-1);
if (left_val > last_val) {
ans[i] = last_val - st.get_min(l);
} else {
ans[i] = c[i] - st.get_max(l) + last_val;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
28372 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
28464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1381 ms |
42568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
28372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
28372 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
28464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
