#include <bits/stdc++.h>
using namespace std;
#include "candies.h"
//#define int long long
typedef long long ll;
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll cap;
struct dat{
ll cur_sum, tot, mx, mn, mxpos, mnpos;
};
dat comb(dat a, dat b){
dat ans;
ans.tot = a.tot + b.tot;
if(b.mnpos < b.mxpos){
if(a.cur_sum + b.mn < 0){
if(b.mx - b.mn > cap)ans.cur_sum = cap + b.tot - b.mx;
else ans.cur_sum = b.tot - b.mn;
}
else if(a.cur_sum + b.mx > cap){
ans.cur_sum = cap + b.tot - b.mx;
}
else ans.cur_sum = a.cur_sum + b.tot;
}
else{
if(a.cur_sum + b.mx > cap){
if(b.mn - b.mx < -cap)ans.cur_sum = b.tot - b.mn;
else ans.cur_sum = cap + b.tot - b.mx;
}
else if(a.cur_sum + b.mn < 0){
ans.cur_sum = b.tot - b.mn;
}
else ans.cur_sum = a.cur_sum + b.tot;
}
ans.mn = min(a.mn, a.tot + b.mn);
ans.mnpos = (ans.mn == a.tot + b.mn ? b.mnpos : a.mnpos);
ans.mx = max(a.mx, a.tot + b.mx);
ans.mxpos = (ans.mx == a.tot + b.mx ? b.mxpos : a.mxpos);
//assert(ans.cur_sum >= 0);
//assert(ans.cur_sum <= cap);
ans.tot += max(0ll, -ans.mn - cap);
ans.tot -= max(0ll, ans.mx - cap);
ans.mx = min(ans.mx, cap);
ans.mn = max(ans.mn, -cap);
return ans;
}
struct node{
int s, e, m;
dat val;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
if(s != e)l = new node(s, m), r = new node(m+1, e);
val.cur_sum = val.mx = val.mn = 0;
val.mxpos = val.mnpos = s;
val.tot = 0;
}
void upd(int p, ll v){
if(s == e){
val.cur_sum = max(v, 0ll);
val.cur_sum = min(val.cur_sum, cap);
ll vv = v;
vv = max(vv, -cap);
vv = min(vv, cap);
val.mx = val.mn = val.tot = vv;
val.mxpos = val.mnpos = s;
}
else{
if(p <= m)l->upd(p, v);
else r->upd(p, v);
val = comb(l->val, r->val);
//cout << s << ' ' << e << '\n';
//cout << val.cur_sum << ' ' << val.mx << ' ' << val.mn << ' ' << val.tot << '\n';
}
}
}*root;
vector <pi> Q[300005];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = (int)c.size(), q = (int)l.size();
cap = c[0];
for(int i = 0; i < q; i++){
Q[l[i]].push_back({i, v[i]});
Q[r[i] + 1].push_back({i, 0});
}
root = new node(0, q - 1);
vector <int> ans(n);
for(int i = 0; i < n; i++){
//cout << i << '\n';
for(auto [a, b] : Q[i]){
root->upd(a, b);
}
ans[i] = root->val.cur_sum;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
7416 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
458 ms |
58964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 2 |
Incorrect |
375 ms |
56716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
7416 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
