#include <bits/stdc++.h>
#include <candies.h>
using namespace std;
struct segtree{
int sz;
vector<int> val;
vector<bool> on;
vector<bool> blocked;
//vector<int> maxpref, minpref, sum, maxrazn, minrazn;
vector<vector<int>> rec;
segtree(vector<int> v)
{
val = v;
sz = 4*(v.size() + 2);
on.resize(sz);
rec.resize(sz, vector<int>(5));
}
vector<int> recalc(vector<int> &v1, vector<int> &v2)
{
vector<int> ans(5);
ans[2] = v1[2] + v2[2];
ans[0] = max(v1[0], v2[0] + v1[2]);
ans[1] = min(v1[1], v2[1] + v1[2]);
ans[3] = max(max(v1[3], v2[3]), v2[0] + v1[2] - v1[1]);
ans[4] = min(min(v1[4], v2[4]), v2[1] + v1[2] - v1[0]);
return ans;
}
void change(int v, int l, int r, int pos)
{
if(pos < l || pos > r)
return;
if(l == r)
{
on[v] = !on[v];
if(on[v])
{
rec[v][2] = val[l];
rec[v][0] = val[l];
rec[v][1] = val[l];
rec[v][3] = rec[v][4] = val[l];
// cout<<rec[v][0]<<" "<<rec[v][1]<<" "<<rec[v][2]<<" "<<rec[v][3]<<" "<<rec[v][4]<<endl;
}
else
rec[v] = {0, 0, 0, 0, 0};
return;
}
change(v*2, l, (l + r) / 2, pos), change(v*2 + 1, (l + r) / 2 + 1, r, pos);
rec[v] = recalc(rec[v*2], rec[v*2 + 1]);
}
int getans(int v, int l, int r, int needmin, int needmax, vector<int> &mrg)
{
if(l == r)
return l;
if(rec[v*2 + 1][0] == 0 && rec[v*2 + 1][1] == 0)
return getans(v*2, l, (l + r) / 2, needmin, needmax, mrg);
vector<int> c = recalc(mrg, rec[v*2]);
if(rec[v*2 + 1][0] + c[2] - c[1] >= needmax || rec[v*2+1][1] + c[2] - c[0] <= needmin || rec[v*2 + 1][3] >= needmax || rec[v*2 + 1][4] <= needmin)
return getans(v * 2 + 1, (l + r) / 2 + 1, r, needmax, needmin, c);
return getans(v, l, (l + r) / 2, needmin, needmax, mrg);
}
int getsum(int v, int l, int r, int l1, int r1)
{
if(l > r1 || l1 > r || l1 > r1)
return 0;
if(l1 <= l && r <= r1)
return rec[v][2];
return getsum(v*2, l, (l + r) / 2, l1, r1) + getsum(v*2 + 1, (l + r) / 2 + 1, r, l1, r1);
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
int n = c.size(), m = l.size();
vector<vector<int>> in(n + 1);
segtree t(v);
for(int i = 0; i < m; i++)
{
in[l[i]].push_back(i);
in[r[i] + 1].push_back(i);
}
vector<int> ans(n);
for(int i = 0; i < n; i++)
{
for(auto j : in[i])
t.change(1, 0, m - 1, j);
int mins = t.rec[1][4], maxs = min(t.rec[1][3], c[i]);
mins = -maxs;
if(mins == 0)
{
ans[i] = min(t.rec[1][2], c[i]);
continue;
}
vector<int> mrg(5);
int pos = t.getans(1, 0, m - 1, mins, maxs, mrg);
ans[i] = t.getsum(1, 0, m - 1, pos + 1, m - 1);
if(t.getsum(1, 0, m - 1, pos, pos) > 0)
ans[i] += maxs;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1469 ms |
67204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
