#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;
template<class T>
istream &operator>>(istream &is, vector<T> &a) {
for (auto &i : a) {
is >> i;
}
return is;
}
struct SegTree {
struct Node {
int sum = 0;
ll mx = -INFLL, mn = INFLL;
ll push = 0;// +=
};
vector<Node> tree;
int n;
SegTree(int n) : n(n) {
tree.resize(4 * n);
}
void push(int v, int l, int r) {
if (l + 1 < r) {
tree[2 * v + 1].push += tree[v].push;
tree[2 * v + 2].push += tree[v].push;
}
tree[v].mx += tree[v].push;
tree[v].mn += tree[v].push;
tree[v].push = 0;
}
Node pull(const Node &vl, const Node &vr) {
Node ans;
ans.sum = vl.sum + vr.sum;
ans.mx = max(vl.mx, vr.mx);
ans.mn = min(vl.mn, vr.mn);
return ans;
}
void update_seg(int v, int l, int r, int li, int ri, ll x) {// +=
push(v, l, r);
if (li >= r || l >= ri) {
return;
}
if (li <= l && r <= ri) {
tree[v].push = x;
push(v, l, r);
return;
}
int m = (l + r) / 2;
update_seg(2 * v + 1, l, m, li, ri, x);
update_seg(2 * v + 2, m, r, li, ri, x);
tree[v] = pull(tree[2 * v + 1], tree[2 * v + 2]);
}
void update_seg(int li, int ri, ll x) {
update_seg(0, 0, n, li, ri, x);
}
void update_point(int v, int l, int r, int i, ll x) {
push(v, l, r);
if (l + 1 == r) {
tree[v].sum = 1;
tree[v].mx = tree[v].mn = x;
return;
}
int m = (l + r) / 2;
{
push(2 * v + 1, l, m);
push(2 * v + 2, m, r);
}
if (i < m) {
update_point(2 * v + 1, l, m, i, x);
} else {
update_point(2 * v + 2, m, r, i, x);
}
tree[v] = pull(tree[2 * v + 1], tree[2 * v + 2]);
}
void update_point(int i, ll x) {
update_point(0, 0, n, i, x);
}
ll get_mn(int v, int l, int r, int li, int ri) {
push(v, l, r);
if (li >= r || l >= ri) {
return INFLL;
}
if (li <= l && r <= ri) {
return tree[v].mn;
}
int m = (l + r) / 2;
return min(get_mn(2 * v + 1, l, m, li, ri), get_mn(2 * v + 2, m, r, li, ri));
}
ll get_mn(int li, int ri) {
return get_mn(0, 0, n, li, ri);
}
ll get_mx(int v, int l, int r, int li, int ri) {
push(v, l, r);
if (li >= r || l >= ri) {
return -INFLL;
}
if (li <= l && r <= ri) {
return tree[v].mx;
}
int m = (l + r) / 2;
return max(get_mx(2 * v + 1, l, m, li, ri), get_mx(2 * v + 2, m, r, li, ri));
}
ll get_mx(int li, int ri) {
return get_mx(0, 0, n, li, ri);
}
int get_sum(int v, int l, int r, int li, int ri) {
push(v, l, r);
if (li >= r || l >= ri) {
return 0;
}
if (li <= l && r <= ri) {
return tree[v].sum;
}
int m = (l + r) / 2;
return get_sum(2 * v + 1, l, m, li, ri) + get_sum(2 * v + 2, m, r, li, ri);
}
int get_sum(int li, int ri) {
return get_sum(0, 0, n, li, ri);
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
freopen("input.txt", "r", stdin);
#endif
int n, m, d;
cin >> n >> m >> d;
vector<int> a(n + m);
cin >> a;
vector<pair<int, int>> coords;
for (int i = 0; i < n + m; ++i) {
coords.push_back({a[i], i});
}
sort(coords.begin(), coords.end());
SegTree st(coords.size());
ll ans = 0;
auto add = [&](int i) {
int it = lower_bound(coords.begin(), coords.end(), pair(a[i], i)) - coords.begin();
st.update_seg(it + 1, st.n, d);
int ii = st.get_sum(0, it);
st.update_point(it, ii * 1ll * d - a[i]);
ll mn = st.get_mn(0, st.n);
ll mx = st.get_mx(0, st.n);
ans = max(ans, mx - mn);
};
for (int i = 0; i < n; ++i) {
add(i);
}
for (int i = n; i < n + m; ++i) {
add(i);
if (ans % 2 == 0) {
cout << ans / 2 << " ";
} else {
cout << ans / 2 << ".5 ";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
242 ms |
29984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
242 ms |
29984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
