#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
using namespace std;
constexpr static int MEMORY_FACTOR = 3;
constexpr static int INF = 1e18;
struct SegTree
{
struct Node
{
int sum, min_prefix, max_prefix, min_index, max_index;
Node(int sum, int min_prefix, int max_prefix, int index) : sum(sum), min_prefix(min_prefix), max_prefix(max_prefix), min_index(index), max_index(index) {}
Node(int sum, int min_prefix, int max_prefix) : Node(sum, min_prefix, max_prefix, -1) {}
Node() : Node(0, 0, 0) {}
bool check(int capacity) {return max_prefix - min_prefix > capacity; }
};
static Node merge(Node l, Node r)
{
Node new_node(l.sum + r.sum, min(l.min_prefix, r.min_prefix + l.sum), max(l.max_prefix, r.max_prefix + l.sum));
if (l.min_prefix < r.min_prefix + l.sum)
new_node.min_index = l.min_index;
else
new_node.min_index = r.min_index;
if (l.max_prefix > r.max_prefix + l.sum)
new_node.max_index = l.max_index;
else
new_node.max_index = r.max_index;
return new_node;
}
int n;
vector<Node> data;
SegTree(int n) : n(n), data(n<<2) {}
void set(int l, int r, int index, int i, int val)
{
if (i >= r || l > i)
return;
if (l + 1 == r)
{
data[index] = Node(val, val, val, i);
return;
}
int mid = (l+r)>>1;
set(l, mid, index<<1, i, val);
set(mid, r, index<<1|1, i, val);
data[index] = merge(data[index<<1], data[index<<1|1]);
}
Node get(int l, int r, int index, int ss, int ee) const
{
if (l >= ee || ss >= r)
return Node(0, INF, -INF);
if (l + 1 == r)
return data[index];
int mid = (l+r)>>1;
Node l_node = get(l, mid, index<<1, ss, ee);
Node r_node = get(mid, r, index<<1|1, ss, ee);
return merge(l_node, r_node);
}
void set(int i, int val) { set(0, n, 1, i, val); }
Node get(int ss, int ee) const { return get(0, n, 1, ss, ee); }
int find_smallest_distance(int cap)
{
if (!data[1].check(cap))
return -1;
int l = 0, r = n, index = 1;
int min_prefix = INF, max_prefix = -INF;
while (r - l > 1)
{
if (max(data[index<<1|1].max_prefix, max_prefix) - min(data[index<<1|1].min_prefix, min_prefix) > cap)
{
l = (l+r)>>1;
index = index<<1|1;
}
else
{
r = (l+r)>>1;
min_prefix = min(data[index<<1|1].min_prefix + data[index<<1].sum, min_prefix);
max_prefix = max(data[index<<1|1].max_prefix + data[index<<1].sum, max_prefix);
}
}
return l;
}
};
vector<array<int,2>> index_sort(const vector<int32_t>& v)
{
vector<array<int, 2>> res(v.size());
for (int i = 0; i < static_cast<int64_t>(v.size()); i++)
res[i] = {v[i], i};
sort(res.begin(), res.end());
return res;
}
/*
int find_min_prefix(const SegTree& st, int ss, int ee)
{
int mp = st.get(ss, ee).min_prefix;
int l = ss, r = ee;
while (r - l > 1)
{
int m = (l+r)>>1;
if (st.get(ss, m).sum + st.get(m, ee).min_prefix == mp)
l = m;
else
r = m;
}
return l;
}
int find_max_prefix(const SegTree& st, int ss, int ee)
{
int mp = st.get(ss, ee).max_prefix;
int l = ss, r = ee;
while (r - l > 1)
{
int m = (l+r)>>1;
if (st.get(ss, m).sum + st.get(m, ee).max_prefix == mp)
l = m;
else
r = m;
}
return l;
}
*/
vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v)
{
for (int32_t& i : r) i++;
vector<array<int,2>> li = index_sort(l), ri = index_sort(r);
int n = v.size()+1;
int m = c.size();
int ll = 0, rr = 0;
SegTree st(n);
vector<int32_t> res(m);
for (int i = 0; i < m; i++)
{
while (ll < static_cast<int64_t>(li.size()) && li[ll][0] == i)
{
int index = li[ll][1];
st.set(index+1, v[index]);
ll++;
}
while (rr < static_cast<int64_t>(ri.size()) && ri[rr][0] == i)
{
int index = ri[rr][1];
st.set(index+1, 0);
rr++;
}
int ss = st.find_smallest_distance(c[i]);
if (ss == -1)
{
int min_index = st.get(0, n).min_index;
res[i] = st.get(min_index + 1, n).sum;
}
else
{
int a = st.get(ss, n).min_index,
b = st.get(ss, n).max_index;
if (a > b)
res[i] = st.get(a+1, n).sum;
else
res[i] = c[i] + st.get(b+1, n).sum;
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5055 ms |
44904 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
