#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 Node
{
int sum, min_prefix, max_prefix;
Node(int sum, int min_prefix, int max_prefix) : sum(sum), min_prefix(min_prefix), max_prefix(max_prefix) {}
bool check(int capacity) {return max_prefix - min_prefix > capacity; }
Node() : Node(0, 0, 0) {}
};
Node merge(Node l, Node r)
{
return Node(l.sum + r.sum, min(l.min_prefix, r.min_prefix + l.sum), max(l.max_prefix, r.max_prefix + l.sum));
}
struct SegTree
{
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);
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); }
};
/*
struct PST
{
int n;
vector<int> l, r;
vector<Node> data;
PST(int n) : n(n)
{
l.reserve(n<<MEMORY_FACTOR);
r.reserve(n<<MEMORY_FACTOR);
data.reserve(n<<MEMORY_FACTOR);
}
int build(int ll, int rr);
Node get(int index, int ll, int rr, int ss, int ee);
int update(int index, int ll, int rr, int i, int val);
};
int PST::build(int ll, int rr)
{
int val = data.size();
data.pb(Node());
l.pb(-1);
r.pb(-1);
if (ll + 1 < rr)
{
int mid = (ll + rr) / 2;
l[val] = build(ll, mid);
r[val] = build(mid, rr);
}
return val;
}
Node PST::get(int index, int ll, int rr, int ss, int ee)
{
if (ll >= ee || ss >= rr)
return Node(0, INF, -INF);
if (rr == ll + 1)
return data[index];
int mid = (ll + rr) / 2;
Node l_res = get(l[index], ll, mid, ss, ee);
Node r_res = get(r[index], mid, rr, ss, ee);
return merge(l_res, r_res);
}
int update(int index, int ll, int rr, int i, int val)
{
int res = data.size();
data.pb(Node());
l.pb(-1);
r.pb(-1);
if (ll + 1 == rr)
{
data[res] = Node(val, val, val);
return res;
}
int mid = (ll + rr) / 2;
if (i < mid)
{
r[res] = r[index];
l[res] = update(l[index], ll, mid, i, val);
}
else
{
l[res] = l[index];
r[res] = update(r[index], mid, rr, i, val);
}
data[res] = merge(data[l[res]], data[r[res]]);
return res;
}
*/
vector<array<int,2>> index_sort(const vector<int>& v)
{
vector<array<int, 2>> res(v.size());
for (int i = 0; i < 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 = r+l>>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 = r+l>>1;
if (st.get(ss, m).sum + st.get(m, ee).max_prefix == mp)
l = m;
else
r = m;
}
return l;
}
int find_smallest_distance(const SegTree& st, int cap, int n)
{
int l = -1, r = n;
while (r - l > 1)
{
int m = r+l>>1;
if (st.get(m, n).check(cap))
l = m;
else
r = m;
}
return l;
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
for (int& 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<int> res(m);
for (int i = 0; i < m; i++)
{
while (ll < li.size() && li[ll][0] == i)
{
int index = li[ll][1];
st.set(index+1, v[index]);
ll++;
}
while (rr < ri.size() && ri[rr][0] == i)
{
int index = ri[rr][1];
st.set(index+1, 0);
rr++;
}
int ss = find_smallest_distance(st, c[i], n);
if (ss == -1)
{
res[i] = st.get(find_min_prefix(st, 0, n) + 1, n).sum;
}
else
{
int a = find_min_prefix(st, ss, n),
b = find_max_prefix(st, ss, n);
if (a > b)
res[i] = st.get(a+1, n).sum;
else
res[i] = c[i] + st.get(b+1, n).sum;
}
}
return res;
}
int32_t main()
{
vector<int> c = {10, 15, 13}, l = {0, 0}, r = {2, 1}, v = {20, -11};
vector<int> res = distribute_candies(c, l, r, v);
for (int i : res)
cout << i << " ";
cout << "\n";
}
Compilation message
candies.cpp: In member function 'void SegTree::set(int64_t, int64_t, int64_t, int64_t, int64_t)':
candies.cpp:37:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int mid = l+r>>1;
| ~^~
candies.cpp: In member function 'Node SegTree::get(int64_t, int64_t, int64_t, int64_t, int64_t) const':
candies.cpp:48:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | int mid = l+r>>1;
| ~^~
candies.cpp: In function 'std::vector<std::array<long int, 2> > index_sort(const std::vector<long int>&)':
candies.cpp:131:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
candies.cpp: In function 'int64_t find_min_prefix(const SegTree&, int64_t, int64_t)':
candies.cpp:144:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
144 | int m = r+l>>1;
| ~^~
candies.cpp: In function 'int64_t find_max_prefix(const SegTree&, int64_t, int64_t)':
candies.cpp:159:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
159 | int m = r+l>>1;
| ~^~
candies.cpp: In function 'int64_t find_smallest_distance(const SegTree&, int64_t, int64_t)':
candies.cpp:173:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
173 | int m = r+l>>1;
| ~^~
candies.cpp: In function 'std::vector<long int> distribute_candies(std::vector<long int>, std::vector<long int>, std::vector<long int>, std::vector<long int>)':
candies.cpp:193:13: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
193 | while (ll < li.size() && li[ll][0] == i)
| ~~~^~~~~~~~~~~
candies.cpp:199:13: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | while (rr < ri.size() && ri[rr][0] == i)
| ~~~^~~~~~~~~~~
/usr/bin/ld: /tmp/ccgQv5Fh.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccucXizf.o:candies.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccgQv5Fh.o: in function `main':
grader.cpp:(.text.startup+0x30e): undefined reference to `distribute_candies(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
