#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> merge(vector<ll> v1, vector<ll> v2)
{
vector<ll> ans(5);
ans[0] = v1[0] + v2[0];
if(v1[1] < v2[1] + v1[0])
ans[1] = v1[1], ans[2] = v1[2];
else
ans[1] = v2[1] + v1[0], ans[2] = v2[2];
if(v1[3] > v2[3] + v1[0])
ans[3] = v1[3], ans[4] = v1[4];
else
ans[3] = v2[3] + v1[0], ans[4] = v2[4];
return ans;
}
struct segtree{
int sz;
vector<int> val;
vector<int> active;
vector<vector<ll>> data;
//sum - data[0]
//minpref - data[1]
//minind - data[2]
//maxpref - data[3]
//maxind - data[4]
segtree(vector<int> v)
{
val = v;
int sz = val.size() * 4 + 2;
active.resize(sz);
data.resize(sz, vector<ll>(5));
}
void change(int v, int l, int r, int pos)
{
if(l > pos || r < pos)
return;
if(l == r)
{
active[v] = !active[v];
if(active[v])
{
data[v][0] = data[v][1] = data[v][3] = val[l];
data[v][2] = l;
data[v][4] = l;
}
else
data[v] = vector<ll>(5);
return;
}
change(v*2, l, (l + r) / 2, pos), change(v*2 + 1, (l + r) / 2 + 1, r, pos);
if(active[v * 2])
{
active[v] = 1;
if(active[v * 2 + 1])
data[v] = merge(data[v*2], data[v*2 + 1]);
else
data[v] = data[v*2];
}
else if(active[v*2 + 1])
data[v] = data[v*2 + 1], active[v] = 1;
}
pair<int, bool> getans(int v, int l, int r, int needmin, int needmax, vector<ll> d)
{
if(!active[v] || (data[v][1] > needmin && data[v][3] < needmax))
return {-1, 0};
if(l == r)
{
if(d[0] == -1e18)
d = data[v];
else
d = merge(data[v], d);
if(d[1] <= needmin)
return {l, 0};
else
return {l, 1};
}
vector<ll> c;
if(d[0] == -1e18)
c = data[v * 2 + 1];
else
c = merge(data[v * 2 + 1], d);
if(active[v * 2 + 1] && (c[1] <= needmin || c[3] >= needmax))
return getans(v*2 + 1, (l + r) / 2 + 1, r, needmin, needmax, d);
return getans(v * 2, l, (l + r) / 2, needmin, needmax, c);
}
void getinfo(int v, int l, int r, int l1, int r1, vector<ll> &d)
{
if(l > r1 || l1 > r || !active[v])
return;
if(l1 <= l && r <= r1)
{
if(d[0] == -1e18)
d = data[v];
else
d = merge(d, data[v]);
}
getinfo(v*2, l, (l + r) / 2, l1, r1, d), getinfo(v*2 + 1, (l + r) / 2 + 1, r, l1, r1, d);
}
};
vector<ll> info(segtree &t, int l, int r, int m)
{
vector<ll> d(5);
d[0] = -1e18;
r = min(r, m);
if(l <= r)
t.getinfo(1, 0, m, l, r, d);
if(d[0] == -1e18)
d[0] = 0;
return d;
}
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);
reverse(v.begin(), v.end());
reverse(l.begin(), l.end());
reverse(r.begin(), r.end());
v.push_back(0);
l.push_back(0);
r.push_back(n - 1);
reverse(v.begin(), v.end());
reverse(l.begin(), l.end());
reverse(r.begin(), r.end());
m++;
for(int i = 0; i < m; i++)
{
in[l[i]].push_back(i);
in[r[i] + 1].push_back(i);
}
vector<int> ans(n);
segtree t(v);
for(int i = 0; i < n; i++)
{
for(auto j : in[i])
t.change(1, 0, m - 1, j);
vector<ll> d(5);
d[0] = -1e18;
auto p = t.getans(1, 0, m - 1, -c[i], c[i], d);
if(p.first == -1)
{
ans[i] = info(t, t.data[1][2] + 1, m - 1, m - 1)[0];
continue;
}
if(p.second)
{
auto x = info(t, p.first, m - 1, m - 1);
// cout<<x[4] + 1<<" "<<m - 1<<endl;
int pos = x[4];
ans[i] = (ll)c[i] + info(t, pos + 1, m - 1, m - 1)[0];
}
else
{
auto x = info(t, p.first, m - 1, m - 1);
int pos = x[2];
ans[i] = info(t, pos + 1, m - 1, m - 1)[0];
}
}
return ans;
}
//signed main()
//{
// int n, m;
// cin>>n>>m;
// vector<int> c(n);
// vector<int> l(m), r(m), v(m);
// for(int i = 0; i < n; i++)
// cin>>c[i];
// 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 |
1 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
274 ms |
164120 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
