#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#define T ar<ll, 7>
const int mxN=2e5;
const T ID={-1, -1, -1, -1, -1, -1, -1};
// store {sum, min prefix, max prefix, up, down, suffix max, suffix pre}
int n, q;
vector<int> queries[mxN];
T mk(int x) {
return {x, x, x, max(0, x), min(0, x), max(0, x), min(0, x)};
}
T cmb(T a, T b) {
if (a==ID||b==ID)
return a!=ID?a:b;
return {
a[0]+b[0],
min(a[1], a[0]+b[1]),
max(a[2], a[0]+b[2]),
max({a[3], b[3], a[0]+b[2]-a[1]}),
min({a[4], b[4], a[0]+b[1]-a[2]}),
max(a[5]+b[0], b[5]),
min(a[6]+b[0], b[6]),
};
}
void pr(T a) {
for (int i=0; i<7; ++i)
cout << a[i] << " ";
cout << endl;
}
struct seg_tree {
T st[1<<19];
void upd(int i, T x, int u=1, int l=0, int r=q-1) {
if (l==r) {
st[u]=x;
return;
}
int mid=(l+r)/2;
i<=mid?upd(i, x, 2*u, l, mid):upd(i, x, 2*u+1, mid+1, r);
st[u]=cmb(st[2*u], st[2*u+1]);
}
int qry1(int x, T thing=ID, int u=1, int l=0, int r=q-1) {
T y=cmb(st[u], thing);
if (y==ID||y[3]<x&&y[4]>-x)
return -1;
if (l==r)
return l;
int mid=(l+r)/2;
int rs=qry1(x, thing, 2*u+1, mid+1, r);
if (rs!=-1)
return rs;
return qry1(x, cmb(st[2*u+1], thing), 2*u, l, mid);
}
int qry2(int ql, int x, T thing=ID, int u=1, int l=0, int r=q-1) {
if (r<ql)
return -1;
T y=cmb(st[u], thing);
if (y==ID||y[3]<x&&y[4]>-x)
return -1;
if (l==r)
return l;
int mid=(l+r)/2;
int ls=qry2(ql, x, thing, 2*u, l, mid);
if (ls!=-1)
return ls;
return qry2(ql, x, cmb(thing, st[2*u]), 2*u+1, mid+1, r);
}
T qry3(int ql, int qr, int u=1, int l=0, int r=q-1) {
if (l>qr||r<ql)
return ID;
if (ql<=l&&r<=qr)
return st[u];
int mid=(l+r)/2;
return cmb(qry3(ql, qr, 2*u, l, mid), qry3(ql, qr, 2*u+1, mid+1, r));
}
ll gt(int s, bool t) {
T x=qry3(s, q-1);
//cout << s << " " << t << endl;
//pr(x);
//pr(st[3]);
return x==ID?0:x[5+t];
}
} st;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n=c.size(), q=l.size();
vector<int> ans(n);
for (int i=0; i<q; ++i) {
queries[l[i]].push_back(i);
if (r[i]+1<n)
queries[r[i]+1].push_back(i);
}
memset(st.st, -1, sizeof(st.st));
for (int i=0; i<n; ++i) {
for (int j : queries[i])
st.upd(j, i==l[j]?mk(v[j]):ID);
if (st.st[1]==ID||c[i]>=st.st[1][3]) {
ans[i]=st.gt(0, 0);
continue;
}
int l=st.qry1(c[i]);
assert(~l);
int r=st.qry2(l, c[i]);
assert(~r);
//cout << l << " " << r << endl;
T x=st.qry3(l, r);
if (x[3]>=c[i]) {
assert(x[4]>-c[i]);
ans[i]=c[i]+st.gt(r+1, 1);
} else if (x[4]<=-c[i]) {
assert(x[3]<c[i]);
ans[i]=st.gt(r+1, 0);
} else
assert(0);
}
return ans;
}
Compilation message
candies.cpp: In member function 'int seg_tree::qry1(int, std::array<long long int, 7>, int, int, int)':
candies.cpp:54:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
54 | if (y==ID||y[3]<x&&y[4]>-x)
candies.cpp: In member function 'int seg_tree::qry2(int, int, std::array<long long int, 7>, int, int, int)':
candies.cpp:69:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
69 | if (y==ID||y[3]<x&&y[4]>-x)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
33676 KB |
Output is correct |
| 2 |
Correct |
14 ms |
33620 KB |
Output is correct |
| 3 |
Runtime error |
43 ms |
68324 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
157 ms |
98700 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
68172 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
68204 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
33676 KB |
Output is correct |
| 2 |
Correct |
14 ms |
33620 KB |
Output is correct |
| 3 |
Runtime error |
43 ms |
68324 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
