#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int n, q;
ll add[maxn], rem[maxn];
vector < int > s;
pair < int, int > cap[maxn];
struct lazy_node
{
ll val, set_to_0, set_to_max;
lazy_node()
{
val = set_to_0 = set_to_max = 0;
};
};
ll tree[4 * maxn];
lazy_node lazy[4 * maxn];
void push_lazy(int root, int left, int right)
{
if (left == right)
{
if (lazy[root].set_to_0)
tree[root] = 0;
if (lazy[root].set_to_max)
tree[root] = cap[left].first;
tree[root] += lazy[root].val;
lazy[root] = lazy_node();
return;
}
if (lazy[root].set_to_0 || lazy[root].set_to_max)
{
lazy[root * 2] = lazy[root];
lazy[root * 2 + 1] = lazy[root];
}
else
{
lazy[root * 2].val += lazy[root].val;
lazy[root * 2 + 1].val += lazy[root].val;
}
lazy[root] = lazy_node();
}
void update_range(int root, int left, int right, int qleft, int qright, lazy_node cur_lazy)
{
///cout << root << " " << left << " " << right << " " << endl;
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
//cout << tree[root] << endl;
lazy[root] = cur_lazy;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
update_range(root * 2, left, mid, qleft, qright, cur_lazy);
update_range(root * 2 + 1, mid + 1, right, qleft, qright, cur_lazy);
}
ll get_element(int root, int left, int right, int pos)
{
push_lazy(root, left, right);
if (left == right)
return tree[root];
int mid = (left + right) / 2;
if (pos <= mid)
return get_element(root * 2, left, mid, pos);
else
return get_element(root * 2 + 1, mid + 1, right, pos);
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v)
{
n = c.size();
q = l.size();
s.resize(n, 0);
bool all_positive = true, whole = true;
for (int i = 0; i < q; i ++)
{
if (v[i] < 0)
all_positive = false;
if (l[i] != 0 || r[i] != n - 1)
whole = false;
}
if (whole)
{
for (int i = 0; i < n; i ++)
cap[i] = {c[i], i};
sort(cap, cap + n);
for (int i = 0; i < q; i ++)
{
if (v[i] > 0)
{
int lf = 0, rf = n - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
ll val = get_element(1, 0, n - 1, mf);
///cout << lf << " : " << rf << " : " << val << " " << v[i] << " " << cap[mf].first << endl;
if (val + v[i] >= cap[mf].first)
lf = mf + 1;
else
rf = mf - 1;
}
if (rf != -1)
{
lazy_node cur_lazy;
cur_lazy.set_to_max = 1;
update_range(1, 0, n - 1, 0, rf, cur_lazy);
}
if (rf != n - 1)
{
lazy_node cur_lazy;
cur_lazy.val = v[i];
update_range(1, 0, n - 1, rf + 1, n - 1, cur_lazy);
}
}
else
{
int lf = 0, rf = n - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
ll val = get_element(1, 0, n - 1, mf);
if (val + v[i] <= 0)
lf = mf + 1;
else
rf = mf - 1;
}
///cout << rf << endl;
if (rf != -1)
{
lazy_node cur_lazy;
cur_lazy.set_to_0 = 1;
update_range(1, 0, n - 1, 0, rf, cur_lazy);
}
///cout << "here" << endl;
if (rf != n - 1)
{
lazy_node cur_lazy;
cur_lazy.val = v[i];
update_range(1, 0, n - 1, rf + 1, n - 1, cur_lazy);
}
///cout << "stop" << endl;
}
}
for (int i = 0; i < n; i ++)
s[cap[i].second] = get_element(1, 0, n - 1, i);
return s;
}
if (all_positive)
{
for (int i = 0; i < q; i ++)
{
add[l[i]] += v[i];
rem[r[i] + 1] += v[i];
}
ll sum = 0;
for (int i = 0; i < n; i ++)
{
sum += add[i];
sum -= rem[i];
s[i] = min((ll)(c[i]), sum);
}
return s;
}
for (int i = 0; i < q; i ++)
{
for (int j = l[i]; j <= r[i]; j ++)
{
s[j] += v[i];
if (s[j] < 0)
s[j] = 0;
if (s[j] > c[j])
s[j] = c[j];
}
}
return s;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
19080 KB |
Output is correct |
| 2 |
Correct |
8 ms |
19044 KB |
Output is correct |
| 3 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 4 |
Correct |
9 ms |
19040 KB |
Output is correct |
| 5 |
Correct |
13 ms |
19176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
30040 KB |
Output is correct |
| 2 |
Correct |
106 ms |
29996 KB |
Output is correct |
| 3 |
Correct |
108 ms |
30056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
19028 KB |
Output is correct |
| 2 |
Correct |
512 ms |
23828 KB |
Output is correct |
| 3 |
Correct |
484 ms |
23404 KB |
Output is correct |
| 4 |
Execution timed out |
5044 ms |
26060 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
19028 KB |
Output is correct |
| 2 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 3 |
Correct |
306 ms |
23876 KB |
Output is correct |
| 4 |
Correct |
97 ms |
27016 KB |
Output is correct |
| 5 |
Correct |
741 ms |
31492 KB |
Output is correct |
| 6 |
Correct |
739 ms |
35956 KB |
Output is correct |
| 7 |
Correct |
767 ms |
36392 KB |
Output is correct |
| 8 |
Correct |
722 ms |
34900 KB |
Output is correct |
| 9 |
Correct |
446 ms |
36380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
19080 KB |
Output is correct |
| 2 |
Correct |
8 ms |
19044 KB |
Output is correct |
| 3 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 4 |
Correct |
9 ms |
19040 KB |
Output is correct |
| 5 |
Correct |
13 ms |
19176 KB |
Output is correct |
| 6 |
Correct |
111 ms |
30040 KB |
Output is correct |
| 7 |
Correct |
106 ms |
29996 KB |
Output is correct |
| 8 |
Correct |
108 ms |
30056 KB |
Output is correct |
| 9 |
Correct |
8 ms |
19028 KB |
Output is correct |
| 10 |
Correct |
512 ms |
23828 KB |
Output is correct |
| 11 |
Correct |
484 ms |
23404 KB |
Output is correct |
| 12 |
Execution timed out |
5044 ms |
26060 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
