#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct segtree{
int sz;
vector<ll> sum, mins, maxs, sumpush;
segtree(int maxn)
{
sz = maxn*4 + 4;
sum.resize(sz);
mins = maxs = sumpush = sum;
}
void push(int v, int l, int r)
{
mins[v] += sumpush[v];
maxs[v] += sumpush[v];
sum[v] += (ll)(r - l + 1)*sumpush[v];
if(l != r)
sumpush[v*2] += sumpush[v], sumpush[v*2 + 1] += sumpush[v];
sumpush[v] = 0;
}
void add(int v, int l, int r, int l1, int r1, int val)
{
push(v, l, r);
if(l > r1 || l1 > r)
return;
if(l1 <= l && r <= r1)
{
sumpush[v] += val;
push(v, l, r);
return;
}
add(v*2, l, (l + r) / 2, l1, r1, val), add(v*2 + 1, (l + r) / 2 + 1, r, l1, r1, val);
sum[v] = sum[v * 2] + sum[v * 2 + 1];
mins[v] = min(mins[v * 2], mins[v * 2 + 1]);
maxs[v] = max(maxs[v * 2], maxs[v * 2 + 1]);
}
pair<int, bool> getpos(int v, int l, int r, int razn, ll minr, ll maxr)
{
push(v, l, r);
if(l == r)
{
if(mins[v] <= minr)
return {l, 0};
else
return {l, 1};
}
// cout<<razn<<" "<<l<<" "<<r<<endl;
push(v * 2, l, (l + r) / 2);
push(v * 2 + 1, (l + r) / 2 + 1, r);
if(abs(min(minr, mins[v * 2 + 1]) - max(maxr, maxs[v * 2 + 1])) >= razn)
return getpos(v * 2 + 1, (l + r) / 2 + 1, r, razn, minr, maxr);
return getpos(v * 2, l, (l + r) / 2, razn, min(minr, mins[v * 2 + 1]), max(maxr, maxs[v * 2 + 1]));
}
int wheremin(int v, int l, int r, ll need)
{
push(v, l, r);
if(l == r)
return l;
push(v * 2, l, (l + r) / 2);
push(v * 2 + 1, (l + r) / 2 + 1, r);
if(mins[v * 2 + 1] == need)
return wheremin(v * 2 + 1, (l + r ) / 2 + 1, r, need);
return wheremin(v * 2, l, (l + r) / 2, need);
}
int wheremax(int v, int l, int r, ll need)
{
push(v, l, r);
if(l == r)
return l;
push(v * 2, l, (l + r) / 2);
push(v * 2 + 1, (l + r) / 2 + 1, r);
if(maxs[v * 2 + 1] == need)
return wheremax(v * 2 + 1, (l + r ) / 2 + 1, r, need);
return wheremax(v * 2, l, (l + r) / 2, need);
}
ll getmin(int v, int l, int r, int l1, int r1)
{
push(v, l, r);
if(l > r1 || l1 > r || l1 > r1)
return 1e18;
if(l1 <= l && r <= r1)
return mins[v];
return min(getmin(v * 2, l, (l + r) / 2, l1, r1), getmin(v * 2 + 1, (l + r) / 2 + 1, r, l1, r1));
}
ll getmax(int v, int l, int r, int l1, int r1)
{
push(v, l, r);
if(l > r1 || l1 > r || l1 > r1)
return -1e18;
if(l1 <= l && r <= r1)
return maxs[v];
return max(getmax(v * 2, l, (l + r) / 2, l1, r1), getmax(v * 2 + 1, (l + r) / 2 + 1, r, l1, r1));
}
ll getsum(int v, int l, int r, int l1, int r1)
{
push(v, l, r);
if(l > r1 || l1 > r || l1 > r1)
return 0;
if(l1 <= l && r <= r1)
return sum[v];
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);
for(int i = 0; i < m; i++)
{
in[l[i]].push_back(i);
in[r[i] + 1].push_back(i);
}
segtree t(m + 1);
vector<int> active(m);
vector<int> ans(n);
for(int i = 0; i < n; i++)
{
for(auto j : in[i])
{
active[j] ^= 1;
if(active[j])
t.add(1, 0, m, j + 1, m, v[j]);
else
t.add(1, 0, m, j + 1, m, -v[j]);
}
t.push(1, 0, m);
int razn = min((ll)c[i], t.maxs[1] - t.mins[1]);
auto p = t.getpos(1, 0, m, razn, 1e18, -1e18);
if(!p.second)
{
int pos = t.wheremax(1, 0, m, t.getmax(1, 0, m, p.first, m));
ans[i] = razn + t.getsum(1, 0, m, m, m) - t.getsum(1, 0, m, pos, pos);
}
else
{
int pos = t.wheremin(1, 0, m, t.getmin(1, 0, m, p.first, m));
ans[i] = t.getsum(1, 0, m, m, m) - t.getsum(1, 0, m, pos, pos);
}
}
return ans;
}
/*signed main()
{
int n, m;
cin>>n;
vector<int> c(n);
for(int i = 0; i < n; i++)
cin>>c[i];
cin>>m;
vector<int> l(m), r(m), v(m);
for(int i = 0; i < m; i++)
cin>>l[i]>>r[i]>>v[i];
auto a = distribute_candies(c, l, r, v);
for(auto i : a)
cout<<i<<" ";
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1351 ms |
43476 KB |
Output is correct |
| 2 |
Correct |
1408 ms |
47684 KB |
Output is correct |
| 3 |
Correct |
1364 ms |
47372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
489 ms |
36176 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
