#include "candies.h"
#include <iostream>
#include <vector>
#include <array>
#define ll long long
using namespace std;
ll n, q;
vector <array<ll, 2>> Q[200000];
struct SegTree{
ll ans = -1;
struct Node{
ll mx = 0;
ll mn = 0;
ll sum = 0;
ll prefmx = 0;
ll prefmn = 0;
ll sufmx = 0;
ll sufmn = 0;
};
Node st[800000];
void merge(ll id) {
st[id].mx = max(max(st[id*2].mx, st[id*2+1].mx), st[id*2].sufmx + st[id*2+1].prefmx);
st[id].mn = min(min(st[id*2].mn, st[id*2+1].mn), st[id*2].sufmn + st[id*2+1].prefmn);
st[id].sum = st[id*2].sum + st[id*2+1].sum;
st[id].prefmx = max(st[id*2].prefmx, st[id*2].sum+st[id*2+1].prefmx);
st[id].prefmn = min(st[id*2].prefmn, st[id*2].sum+st[id*2+1].prefmn);
st[id].sufmx = max(st[id*2+1].sufmx, st[id*2].sufmx + st[id*2+1].sum);
st[id].sufmn = min(st[id*2+1].sufmn, st[id*2].sufmn + st[id*2+1].sum);
}
void update(ll id, ll l, ll r, ll q, ll w) {
if (l == r) {
st[id] = {max(0LL, w), min(0LL, w), w, max(0LL, w), min(0LL, w), max(0LL, w), min(0LL, w)};
return;
}
ll mid = (l+r)/2;
if (q <= mid) update(id*2, l, mid, q, w);
else update(id*2+1, mid+1, r, q, w);
merge(id);
}
ll query_sum(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql || ql > qr) return 0;
else if (ql <= l && r <= qr) return st[id].sum;
ll mid = (l+r)/2;
return query_sum(id*2, l, mid, ql, qr) + query_sum(id*2+1, mid+1, r, ql, qr);
}
ll solve_mx(ll id, ll l, ll r, ll w, ll rmx) {
if (max(st[id].mx, st[id].sufmx + rmx) <= w) return -1;
else if (l == r) return l;
ll mid = (l+r)/2;
if (st[id*2+1].mx > w || st[id*2+1].sufmx + rmx > w) return solve_mx(id*2+1, mid+1, r, w, rmx);
else return solve_mx(id*2, l, mid, w, max(rmx + st[id*2+1].sum, st[id*2+1].prefmx));
}
ll solve_mn(ll id, ll l, ll r, ll w, ll rmn) {
if (min(st[id].mn, st[id].sufmn + rmn) >= w) return -1;
else if (l == r) return l;
ll mid = (l+r)/2;
if (st[id*2+1].mn < w || st[id*2+1].sufmn + rmn < w) return solve_mn(id*2+1, mid+1, r, w, rmn);
else return solve_mn(id*2, l, mid, w, min(rmn + st[id*2+1].sum, st[id*2+1].prefmn));
}
ll bound_mx(ll id, ll l, ll r, ll q, ll w) {
if (r < q) return 0;
ll mid = (l+r)/2;
if (q <= l) {
//cout << l << " " << r << " " << st[id].sum << " " << w << " " << st[id*2].sum << " " << st[id*2+1].prefmx << endl;
if (st[id].sum > w) ans = max(ans, r);
else if (l != r && st[id*2+1].prefmx > max(0LL, w-st[id*2].sum)) bound_mx(id*2+1, mid+1, r, q, max(0LL, w-st[id*2].sum));
else if (l != r && st[id*2].prefmx > w) bound_mx(id*2, l, mid, q, w);
return st[id].sum;
}
ll z = bound_mx(id*2, l, mid, q, w);
z += bound_mx(id*2+1, mid+1, r, q, w-z);
return z;
}
ll bound_mn(ll id, ll l, ll r, ll q, ll w) {
if (r < q) return 0;
ll mid = (l+r)/2;
if (q <= l) {
if (st[id].sum < w) ans = max(ans, r);
else if (st[id*2+1].prefmn < min(0LL, w-st[id*2].sum)) bound_mn(id*2+1, mid+1, r, q, min(0LL, w-st[id*2].sum));
else if (st[id*2].prefmn < w) bound_mn(id*2, l, mid, q, w);
return st[id].sum;
}
ll z = bound_mn(id*2, l, mid, q, w);
z += bound_mn(id*2+1, mid+1, r, q, w-z);
return z;
}
} ST;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
ll n = c.size(), q = l.size(), a, b, f;
vector <int> F;
for (int i=0; i<q; ++i) {
Q[l[i]].push_back({i, v[i]});
if (r[i] != n-1) Q[r[i]+1].push_back({i, 0});
}
for (int i=0; i<n; ++i) {
for (auto [u, w] : Q[i]) {
ST.update(1, 0, q-1, u, w);
}
ST.ans = -1;
a = ST.solve_mx(1, 0, q-1, c[i], 0);
b = ST.solve_mn(1, 0, q-1, -c[i], 0);
//cout << a << " " << b << " " << ST.st[1].mx << endl;
if (a == -1) {
a = ST.bound_mn(1, 0, q-1, 0, 0);
if (ST.ans == -1) f = ST.query_sum(1, 0, q-1, 0, q-1);
else f = ST.query_sum(1, 0, q-1, ST.ans+1, q-1);
}
else if (a > b) {
ST.bound_mx(1, 0, q-1, a, c[i]);
f = c[i] + ST.query_sum(1, 0, q-1, ST.ans+1, q-1);
}
else {
ST.bound_mn(1, 0, q-1, b, -c[i]);
f = ST.query_sum(1, 0, q-1, ST.ans+1, q-1);
}
F.push_back(f);
}
return F;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
343 ms |
56520 KB |
Output is correct |
| 2 |
Correct |
345 ms |
55720 KB |
Output is correct |
| 3 |
Correct |
345 ms |
55496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 3 |
Runtime error |
136 ms |
103864 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
