#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10;
ll n, m, a[maxn], b[maxn], D, act[2][maxn], used[maxn];
ll pref[maxn], suff[maxn];
pair < ll, ll > p[maxn];
const ll inf = 1e18;
struct segment_tree
{
ll tree[4 * maxn], lazy[maxn];
void build(int root, int left, int right)
{
tree[root] = -inf;
lazy[root] = 0;
if (left == right)
return;
int mid = (left + right) / 2;
build(root * 2, left, mid);
build(root * 2 + 1, mid + 1, right);
}
void push_lazy(int root, int left, int right)
{
tree[root] += lazy[root];
if (left != right)
{
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
}
lazy[root] = 0;
}
void point_update(int root, int left, int right, int pos, ll val)
{
push_lazy(root, left, right);
if (left == right)
{
tree[root] = val;
///cout << "update " << left << " " << right << endl;
return;
}
int mid = (left + right) / 2;
if (pos <= mid)
point_update(root * 2, left, mid, pos, val);
else
point_update(root * 2 + 1, mid + 1, right, pos, val);
tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
}
void range_update(int root, int left, int right, int qleft, int qright, ll val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] = val;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
range_update(root * 2, left, mid, qleft, qright, val);
range_update(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
}
ll query(int root, int left, int right, int qleft, int qright)
{
if (left > qright || right < qleft)
return -inf;
if (left >= qleft && right <= qright)
return tree[root];
int mid = (left + right) / 2;
return max(query(root * 2, left, mid, qleft, qright),
query(root * 2 + 1, mid + 1, right, qleft, qright));
}
};
segment_tree pref_seg, suff_seg;
int fen[maxn];
void add(int v)
{
for (int i = v; i <= n + m; i += (i & -i))
fen[i] ++;
}
int get_sum(int v)
{
int s = 0;
for (int i = v; i > 0; i -= (i & -i))
s += fen[i];
return s;
}
void solve()
{
cin >> n >> m >> D;
for (int i = 1; i <= n; i ++)
cin >> a[i], p[i] = {a[i], i};
for (int j = 1; j <= m; j ++)
cin >> b[j], p[n + j] = {b[j], n + j};
sort(p + 1, p + n + m + 1);
for (int i = 1; i <= n + m; i ++)
{
if (p[i].second <= n)
{
act[0][p[i].second] = i;
}
else
{
act[1][p[i].second - n] = i;
}
}
pref_seg.build(1, 1, n + m);
suff_seg.build(1, 1, n + m);
ll ans = 0;
for (ll i = 1; i <= n + m; i ++)
{ ll idx;
if (i <= n)
idx = act[0][i];
else
idx = act[1][i - n];
ll cnt = get_sum(idx);
add(idx);
pref_seg.point_update(1, 1, n + m, idx, + p[idx].first - cnt * D);
suff_seg.point_update(1, 1, n + m, idx, - p[idx].first + cnt * D);
//cout << i << " : " << pref[idx] << " " << suff[idx] << " " << cnt << " " << idx << endl;
pref_seg.range_update(1, 1, n + m, idx + 1, n + m, -D);
suff_seg.range_update(1, 1, n + m, idx + 1, n + m, +D);
/**for (int j = idx + 1; j <= n + m; j ++)
{
if (!used[j])
continue;
pref[j] = pref[j] - D;
suff[j] = suff[j] + D;
}*/
ll mx_pref = -1e18, mx_suff = -1e18;
mx_pref = pref_seg.query(1, 1, n + m, 1, idx);
mx_suff = suff_seg.query(1, 1, n + m, idx, n + m);
/**for (int j = 1; j < idx; j ++)
{
if (!used[j])
continue;
///cout << "pref " << suff[idx] + pref[j] << " " << pref[j] << endl;
mx_pref = max(mx_pref, pref[j]);
///ans = max(ans, suff[idx] + pref[j]);
}
for (int j = idx + 1; j <= n + m; j ++)
{
if (!used[j])
continue;
mx_suff = max(mx_suff, suff[j]);
///ans = max(ans, pref[idx] + suff[j]);
}*/
ans = max(ans, mx_pref + mx_suff);
///cout << ans << endl;
//cout << endl;
//cout << mx_pref << " :: " << mx_suff << endl;
if (i > n)
{
if (ans % 2 == 0)
cout << ans / 2 << " ";
else
cout << ans / 2 << ".5 ";
}
}
cout << endl;
}
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int main()
{
speed();
solve();
return 0;
}
Compilation message
Main.cpp: In member function 'void segment_tree::build(int, int, int)':
Main.cpp:22:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
22 | if (left == right)
| ^~
Main.cpp:24:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
24 | int mid = (left + right) / 2;
| ^~~
| # |
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 |
225 ms |
24108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
225 ms |
24108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
