#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> merge(vector<ll> v1, vector<ll> v2)
{
vector<ll> ans(7);
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];
ans[5] = min(min(v1[5], v2[5]), min(ans[1], v2[1] + v1[0] - v1[3]));
ans[6] = max(max(v1[6], v2[6]), max(ans[3], v2[3] + v1[0] - v1[1]));
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]
//minrazn - data[5]
//maxrazn - data[6]
segtree(vector<int> v)
{
val = v;
sz = val.size() * 4 + 2;
active.resize(sz);
data.resize(sz, vector<ll>(7));
}
void change(int v, int l, int r, int pos)
{
if(l > pos || r < pos)
return;
if(l == r)
{
active[v] ^= 1;
if(active[v])
{
data[v][0] = data[v][1] = data[v][3] = val[l];
data[v][5] = val[l];
data[v][6] = val[l];
data[v][2] = l;
data[v][4] = l;
}
else
data[v] = vector<ll>(7), data[v][2] = data[v][4] = l;
return;
}
change(v*2, l, (l + r) / 2, pos), change(v*2 + 1, (l + r) / 2 + 1, r, pos);
data[v] = merge(data[v*2], data[v*2 + 1]);
}
pair<int, bool> getans(int v, int l, int r, int needmin, int needmax, vector<ll> d)
{
if(l == r)
{
if(d[0] == -1e18)
d = data[v];
else
d = merge(data[v], d);
if(d[5] <= needmin)
return {l, 0};
else if(d[6] >= needmax)
return {l, 1};
return {-1, 0};
}
vector<ll> c;
if (d[0] == -1e18)
c = data[v * 2 + 1];
else
c = merge(data[v * 2 + 1], d);
if(c[5] <= needmin || c[6] >= 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)
return;
if(l1 <= l && r <= r1)
{
if(d[0] == -1e18)
d = data[v];
else
d = merge(d, data[v]);
return;
}
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(7);
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, d[2] = r, d[4] = r;
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);
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 < m; i++)
{
t.change(1, 0, m - 1, i);
t.change(1, 0, m - 1, i);
}
for(int i = 0; i < n; i++)
{
for(auto j : in[i])
t.change(1, 0, m - 1, j);
vector<ll> d(7);
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);
ll sum = c[i];
for(int j = x[4] + 1; j < m; j++) {
sum += info(t, j, j, m - 1)[0];
}
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;
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<<" ";
}
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
12 ms |
1032 KB |
Output is correct |
| 5 |
Correct |
21 ms |
1100 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3334 ms |
91204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
324 KB |
Output is correct |
| 2 |
Execution timed out |
5039 ms |
80616 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
12 ms |
1032 KB |
Output is correct |
| 5 |
Correct |
21 ms |
1100 KB |
Output is correct |
| 6 |
Incorrect |
3334 ms |
91204 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
