#include "candies.h"
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
using ll = long long;
constexpr int N = 2e5 + 2;
constexpr int block = 450;
struct BLOCKSQRT
{
int n, t[block], in[N];
ll c[N], lazy[N], st[block];
int piv, beg[block], en[block];
BLOCKSQRT()
{
memset(t, -1, sizeof t);
}
void Build()
{
for (int i = 1; i <= n; ++i)
{
in[i] = i / block;
if (!beg[in[i]])
beg[in[i]] = i;
en[in[i]] = i;
}
}
ll Get(int x)
{
return (t[in[x]] ? (t[in[x]] == -1 ? 0 : c[x]) : lazy[x]) + st[in[x]];
}
void Update(int l, int r, int v)
{
if (l > r)
return;
if (t[in[l]])
{
for (int i = beg[in[l]]; i <= en[in[l]]; ++i)
lazy[i] = t[in[l]] == -1 ? 0 : c[i];
t[in[l]] = 0;
}
for (int i = l; i <= en[in[l]] && i <= r; ++i)
lazy[i] += v;
if (in[l] != in[r])
{
for (int i = in[l] + 1; i < in[r]; ++i)
st[i] += v;
if (t[in[r]])
{
for (int i = beg[in[r]]; i <= en[in[r]]; ++i)
lazy[i] = t[in[r]] == -1 ? 0 : c[i];
t[in[r]] = 0;
}
for (int i = beg[in[r]]; i <= r; ++i)
lazy[i] += v;
}
}
void Assign(int l, int r, int v)
{
if (l > r)
return;
for (int i = beg[in[l]]; i <= en[in[l]]; ++i)
lazy[i] = (t[in[l]] ? (t[in[l]] == -1 ? 0 : c[i]) : lazy[i]) + st[in[l]];
t[in[l]] = st[in[l]] = 0;
for (int i = l; i <= en[in[l]] && i <= r; ++i)
lazy[i] = (v == 1 ? c[i] : 0);
if (in[l] != in[r])
{
for (int i = in[l] + 1; i < in[r]; ++i)
{
t[i] = v;
st[i] = 0;
}
for (int i = beg[in[r]]; i <= en[in[r]]; ++i)
lazy[i] = (t[in[r]] ? (t[in[r]] == -1 ? 0 : c[i]) : lazy[i]) + st[in[r]];
st[in[r]] = t[in[r]] = 0;
for (int i = beg[in[r]]; i <= r; ++i)
lazy[i] = (v == 1 ? c[i] : 0);
}
}
void SetFull(int l, int r)
{
Assign(l, r, 1);
}
void SetEmpty(int l, int r)
{
Assign(l, r, -1);
}
} f;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
int n = c.size(), q = r.size();
vector<int> ans(n, 0), id(n, 0), rev(n, 0);
vector<ll> tmp(n, 0);
/*Sub1*/
if (1ll * n * q <= 2e7)
{
for (int i = 0; i < q; ++i)
{
for (int j = l[i]; j <= r[i]; ++j)
ans[j] = max(0, min(c[j], ans[j] + v[i]));
}
return ans;
}
/*Sub2*/
{
for (auto i : v)
if (i < 0)
goto noSub2;
for (int i = 0; i < q; ++i)
{
tmp[l[i]] += v[i];
if (r[i] < n - 1)
tmp[r[i] + 1] -= v[i];
}
for (int i = 0; i < n; ++i)
{
if (i)
tmp[i] += tmp[i - 1];
ans[i] = min((ll)c[i], tmp[i]);
}
return ans;
}
noSub2:;
/*Sub4*/
{
for (auto i : l)
if (i != 0)
goto noSub4;
for (auto i : r)
if (i != n - 1)
goto noSub4;
for (int i = 0; i < n; ++i)
id[i] = i;
sort(id.begin(), id.end(), [&](const int &x, const int &y)
{ return c[x] < c[y]; });
f.n = f.piv = n;
for (int i = 0; i < n; ++i)
f.c[rev[id[i]] = i + 1] = c[id[i]];
f.Build();
for (int i = 0; i < q; ++i)
if (v[i] < 0)
{
int left = 1, mid, right = n;
while (left <= right)
{
mid = (left + right) / 2;
if (f.Get(mid) <= -v[i])
left = mid + 1;
else
right = mid - 1;
}
f.SetEmpty(1, right);
f.Update(left, n, v[i]);
}
else if (v[i] > 0)
{
int left = 1, mid, right = n;
while (left <= right)
{
mid = (left + right) / 2;
if (f.c[mid] - f.Get(mid) <= v[i])
left = mid + 1;
else
right = mid - 1;
}
f.SetFull(1, right);
f.Update(left, n, v[i]);
}
for (int i = 0; i < n; ++i)
ans[i] = f.Get(rev[i]);
return ans;
}
noSub4:;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
4 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
10416 KB |
Output is correct |
| 2 |
Correct |
134 ms |
10536 KB |
Output is correct |
| 3 |
Correct |
123 ms |
10460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
67 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
426 ms |
5104 KB |
Output is correct |
| 4 |
Correct |
88 ms |
8764 KB |
Output is correct |
| 5 |
Correct |
524 ms |
13740 KB |
Output is correct |
| 6 |
Correct |
555 ms |
13960 KB |
Output is correct |
| 7 |
Correct |
544 ms |
13864 KB |
Output is correct |
| 8 |
Correct |
539 ms |
13692 KB |
Output is correct |
| 9 |
Correct |
128 ms |
10416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
4 ms |
332 KB |
Output is correct |
| 6 |
Correct |
135 ms |
10416 KB |
Output is correct |
| 7 |
Correct |
134 ms |
10536 KB |
Output is correct |
| 8 |
Correct |
123 ms |
10460 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Incorrect |
67 ms |
4940 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
