#include "candies.h"
#include <bits/stdc++.h>
#include "grader.cpp"
using namespace std;
using i64 = long long;
struct SegmentTree {
int n;
struct Node {
i64 lazy, mn, mx;
Node() {
lazy = 0;
mn = mx = 0;
}
};
vector<Node> st;
SegmentTree(int n) : n(n) {
st.resize(4 * n);
}
void push(int node) {
st[2 * node + 1].lazy += st[node].lazy;
st[2 * node + 2].lazy += st[node].lazy;
st[2 * node + 1].mn += st[node].lazy;
st[2 * node + 2].mn += st[node].lazy;
st[2 * node + 1].mx += st[node].lazy;
st[2 * node + 2].mx += st[node].lazy;
st[node].lazy = 0;
}
void update(int l, int r, int x) {
update(l, r, x, 0, 0, n - 1);
}
void update(int l, int r, int x, int node, int lx, int rx) {
if (lx > r || rx < l) return;
if (l <= lx && rx <= r) {
st[node].lazy += x;
st[node].mn += x;
st[node].mx += x;
return;
}
push(node);
int mid = (lx + rx) / 2;
update(l, r, x, 2 * node + 1, lx, mid);
update(l, r, x, 2 * node + 2, mid + 1, rx);
st[node].mn = min(st[2 * node + 1].mn, st[2 * node + 2].mn);
st[node].mx = max(st[2 * node + 1].mx, st[2 * node + 2].mx);
}
array<i64, 3> getSuffix(int c) {
return getSuffix(c, 1e18, -1e18, 0, 0, n - 1);
}
array<i64, 3> getSuffix(int c, i64 mn, i64 mx, int node, int lx, int rx) {
if (lx == rx) return {lx, mn, mx};
push(node);
int mid = (lx + rx) / 2;
i64 newMx = max(mx, st[2 * node + 2].mx);
i64 newMn = min(mn, st[2 * node + 2].mn);
if (newMx - newMn > c) {
return getSuffix(c, mn, mx, 2 * node + 2, mid + 1, rx);
} else {
return getSuffix(c, newMn, newMx, 2 * node + 1, lx, mid);
}
}
i64 get(int i) {
return get(i, 0, 0, n - 1);
}
i64 get(int i, int node, int lx, int rx) {
if (lx == rx) return st[node].mn;
push(node);
int mid = (lx + rx) / 2;
if (i <= mid) {
return get(i, 2 * node + 1, lx, mid);
} else {
return get(i, 2 * node + 2, mid + 1, rx);
}
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size();
int q = v.size();
vector<vector<int>> query(n);
for (int i = 0; i < q; ++i) {
query[l[i]].push_back(i);
if (r[i] + 1 < n) {
query[r[i] + 1].push_back(i);
}
}
vector<int> s(n);
SegmentTree st(q + 1);
for (int i = 0; i < n; ++i) {
for (auto j : query[i]) {
if (l[j] == i) {
st.update(j + 1, q, v[j]);
} else {
st.update(j + 1, q, -v[j]);
}
}
i64 ans = st.get(q);
if (st.st[0].mn >= 0 && st.st[0].mx <= c[i]) {
s[i] = ans;
} else {
auto [j, mn, mx] = st.getSuffix(c[i]);
if (st.get(j) < mn) {
s[i] = c[i] - (mx - ans);
} else {
s[i] = ans - mn;
}
}
}
return s;
}
Compilation message
/usr/bin/ld: /tmp/cc3Bk2FN.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc28EgKO.o:candies.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
