#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define md ((l + r) >> 1)
#define SZ(x) (int) x.size()
struct node {
ll pos, neg;
int cnt, lazy;
node(ll x) {
pos = x;
neg = -x;
cnt = 1;
lazy = 0;
}
node() {pos = neg = -1e18; cnt = lazy = 0;}
friend node operator+(const node &l, const node &r) {
node ret;
ret.pos = max(l.pos, r.pos);
ret.neg = max(l.neg, r.neg);
ret.cnt = l.cnt + r.cnt;
return ret;
}
} seg[1 << 19];
void process(int i, int l, int r) {
if (l != r) {
for (auto c : {i << 1, i << 1 | 1}) {
seg[c].lazy += seg[i].lazy;
}
}
seg[i].pos += seg[i].lazy;
seg[i].neg -= seg[i].lazy;
seg[i].lazy = 0;
}
void add(int i, int l, int r, int s, int e, ll v) {
process(i, l, r);
if (s <= l && r <= e) {
seg[i].lazy += v;
process(i, l, r);
return;
}
if (r < s || e < l) {
return;
}
add(i << 1, l, md, s, e, v);
add(i << 1 | 1, md + 1, r, s, e, v);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
ll mx = -1e18;
ll d;
void upd(int i, int l, int r, int x, ll v, ll pos) {
process(i, l, r);
if (l == r) {
seg[i].pos = max(seg[i].pos, d * pos - v);
seg[i].neg = max(seg[i].neg, -(d * pos - v));
mx = max(mx, seg[i].pos + seg[i].neg);
seg[i].cnt++;
return;
}
if (x <= md) {
upd(i << 1, l, md, x, v, pos);
} else {
upd(i << 1 | 1, md + 1, r, x, v, pos + seg[i << 1].cnt);
}
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
node get(int i, int l, int r, int s, int e) {
if (s <= l && r <= e) {
return seg[i];
}
if (r < s || e < l) {
return node();
}
return get(i << 1, l, md, s, e) + get(i << 1 | 1, md + 1, r, s, e);
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m >> d;
int a[n], b[m];
vector<int> v;
for (int i = 0; i < n; i++) {
cin >> a[i];
v.push_back(a[i]);
}
for (int i = 0; i < m; i++) {
cin >> b[i];
v.push_back(b[i]);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
auto insert = [&] (int x) {
int pos = lower_bound(v.begin(), v.end(), x) - v.begin();
add(1, 0, v.size() - 1, pos, v.size() - 1, d);
upd(1, 0, v.size() - 1, pos, x, 0);
mx = max(mx, get(1, 0, v.size() - 1, pos, v.size() - 1).pos + (pos - 1 >= 0? get(1, 0, v.size() - 1, 0, pos - 1).neg : 0));
mx = max(mx, (pos + 1 < SZ(v)? get(1, 0, v.size() - 1, pos + 1, v.size() - 1).pos : 0) + get(1, 0, v.size() - 1, 0, pos).neg);
return mx;
};
for (int i = 0; i < n; i++) {
mx = max(mx, insert(a[i]));
}
for (int i = 0; i < m; i++) {
mx = max(mx, insert(b[i]));
ll v = max(mx, 0ll);
if (v & 1) {
cout << v / 2 << ".5 ";
} else {
cout << v / 2 << ' ';
}
}
cout << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
252 ms |
17348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
252 ms |
17348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
