#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<ll,ll> pll;
using namespace std;
const int N = 200'020;
ll a[N], b[N], D;
int n, m;
vector<pll> cmper;
namespace seg {
struct {
ll mn, mx, cst;
} t[N*4];
int sz;
void merge(int i) {
if (t[2*i+1].cst == -1) {
t[i] = t[2*i+2];
return;
}
if (t[2*i+2].cst == -1) {
t[i] = t[2*i+1];
return;
}
auto l = t[2*i+1];
auto r = t[2*i+2];
if (l.cst < r.cst) {
ll x = r.mn - D - l.mx;
if (abs(x) > r.cst - l.cst) {
auto tmp = r.cst - l.cst;
if (x < 0)
tmp = -tmp;
x = tmp;
}
l.mn += x;
l.mx += x;
l.cst += abs(x);
}
if (r.cst < l.cst) {
ll x = l.mx + D - r.mn;
if (abs(x) > l.cst - r.cst) {
auto tmp = l.cst - r.cst;
if (x < 0)
tmp = -tmp;
x = tmp;
}
r.mn += x;
r.mx += x;
r.cst += abs(x);
}
t[i].mn = l.mn;
t[i].mx = r.mx;
t[i].cst = max(l.cst, r.cst);
if (r.mn - l.mx < D) {
ll x = D - (r.mn - l.mx);
assert(x%2 == 0);
x /= 2;
t[i].cst += x;
t[i].mn -= x;
t[i].mx += x;
}
}
void init(int n) {
sz = n;
fill(t, t+4*sz, typeof(*t){ -1, -1, -1 });
}
void up(int p, ll x, int i, int b, int e) {
if (e-b == 1) {
t[i] = { .mn = x, .mx = x, .cst = 0 };
return;
}
if (p < (b+e)/2)
up(p, x, 2*i+1, b, (b+e)/2);
else
up(p, x, 2*i+2, (b+e)/2, e);
merge(i);
}
void up(int p, ll x) { up(p, x, 0, 0, sz); }
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> m >> D;
D *= 2;
Loop (i,0,n) {
cin >> a[i];
a[i] *= 2;
cmper.push_back({a[i], i});
}
Loop (i,0,m) {
cin >> b[i];
b[i] *= 2;
cmper.push_back({b[i], i+n});
}
sort(cmper.begin(), cmper.end());
seg::init(n + m);
Loop (i,0,n) {
int pos = lower_bound(cmper.begin(), cmper.end(), pll{a[i], i}) - cmper.begin();
seg::up(pos, a[i]);
}
Loop (i,0,m) {
int pos = lower_bound(cmper.begin(), cmper.end(), pll{b[i], i+n}) - cmper.begin();
seg::up(pos, b[i]);
ll x = seg::t[0].cst;
cout << x/2;
if (x%2)
cout << ".5";
cout << ' ';
}
cout << '\n';
}
Compilation message
Main.cpp: In function 'void seg::init(int)':
Main.cpp:68:19: error: 'typeof' was not declared in this scope
68 | fill(t, t+4*sz, typeof(*t){ -1, -1, -1 });
| ^~~~~~
