#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<int> vi;
typedef signed i32;
typedef vector<i32> vi32;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef set<int> si;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define ALL(x) begin(x), end(x)
#define sz(x) (int)x.size()
bool debug = 1;
// en de segment tree bevat een suffix sum, suffix max en suffix min over de queries
class node
{
public:
int sufMax = 0, sufMin = 0, mxIx = 0, mnIx = 0;
node operator+(const node &b) const
{
node res;
if (this->sufMax == LLONG_MIN / 2)
return b;
if (b.sufMax == LLONG_MIN / 2)
return *this;
if (this->sufMin < b.sufMin)
{
res.sufMin = this->sufMin;
res.mnIx = this->mnIx;
}
else
{
res.sufMin = b.sufMin;
res.mnIx = b.mnIx;
}
if (this->sufMax > b.sufMax)
{
res.sufMax = this->sufMax;
res.mxIx = this->mxIx;
}
else
{
res.sufMax = b.sufMax;
res.mxIx = b.mxIx;
}
return res;
}
node &operator+=(const int &v)
{
this->sufMin += v;
this->sufMax += v;
return *this;
}
bool operator==(const node &b)
{
return b.sufMax == this->sufMax &&
b.sufMin == this->sufMin;
}
};
node def = {LLONG_MIN / 2, LLONG_MAX / 2, 0, 0}; // default
vector<node> tree;
vi lazy;
vi treeArr;
int treeSz = 1;
void propagate(int i)
{
tree[i] += lazy[i];
if (i < treeSz)
{
lazy[2 * i] += lazy[i];
// tree[2 * i] += lazy[i]; // new
lazy[2 * i + 1] += lazy[i];
// tree[2 * i + 1] += lazy[i]; // new
}
lazy[i] = {};
}
node get(int i, int l, int r, int ql, int qr)
{
if (qr < l || r < ql)
return def;
node res = def;
if (debug)
{
for (int ix = max(ql, l); ix <= min(qr, r); ix++)
{
if (treeArr[ix] > res.sufMax)
{
res.sufMax = treeArr[ix];
res.mxIx = ix;
}
if (treeArr[ix] < res.sufMin)
{
res.sufMin = treeArr[ix];
res.mnIx = ix;
}
}
}
int m = l + (r - l) / 2;
propagate(i);
if (ql <= l && r <= qr)
{
if (debug)
assert(tree[i] == res);
return tree[i];
}
auto res2 = get(2 * i, l, m, ql, qr) +
get(2 * i + 1, m + 1, r, ql, qr);
if (debug)
assert(res == res2);
return res2;
}
void add(int i, int l, int r, int ql, int qr, int v)
{
if (debug && i == 1)
{
for (int ix = ql; ix <= qr; ix++)
{
treeArr[ix] += v;
}
}
if (qr < l || r < ql)
return;
int m = l + (r - l) / 2;
propagate(i);
if (ql <= l && r <= qr)
{
lazy[i] += v;
propagate(i); // dit miste
return;
}
add(2 * i, l, m, ql, qr, v);
add(2 * i + 1, m + 1, r, ql, qr, v);
tree[i] = tree[2 * i] + tree[2 * i + 1]; // dit miste
}
vi32 distribute_candies(vi32 c, vi32 l, vi32 r, vi32 v)
{
int n = sz(c);
int q = sz(l);
if (debug)
treeArr = vi(q + 1);
while (treeSz <= q)
treeSz *= 2;
tree.resize(treeSz * 2);
lazy.resize(treeSz * 2);
loop(treeSz, i)
{
tree[treeSz + i].mxIx = i;
tree[treeSz + i].mnIx = i;
}
for (int i = treeSz - 1; i >= 1; i--)
{
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
vvi queryBegin(n), queryEnd(n);
loop(q, i)
{
queryBegin[l[i]].pb(i);
queryEnd[r[i]].pb(i);
}
vi32 s(n);
loop(n, i)
{
for (int j : queryBegin[i])
{
add(1, 0, treeSz - 1, 0, j, v[j]);
}
int lo = 0, hi = q;
while (hi > lo)
{
int m = lo + (hi - lo + 1) / 2;
node res = get(1, 0, treeSz - 1, m, q);
int d = res.sufMax - res.sufMin;
if (d >= c[i])
{
lo = m;
}
else
hi = m - 1;
}
node res = get(1, 0, treeSz - 1, hi, q);
int d = res.sufMax - res.sufMin;
if (d >= c[i])
{
if (hi == res.mxIx)
{
s[i] = c[i] + (i32)res.sufMin;
if (debug)
assert(s[i] >= 0);
}
else
{
s[i] = (i32)res.sufMax;
if (debug)
assert(s[i] >= 0);
}
}
else
{
s[i] = (i32)res.sufMax;
}
for (int j : queryEnd[i])
{
add(1, 0, treeSz - 1, 0, j, -v[j]);
}
}
return s;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
156 ms |
97636 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Execution timed out |
5084 ms |
32360 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
