#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;
int cnt;
} t[N*4];
int sz;
void mv(__typeof__(*t) &v, ll x) {
ll mochale = (v.mx - v.mn) - (v.cnt-1)*D;
v.mn += x;
v.mx += x;
v.cst += abs(x);
if (x > 0)
v.mx -= min(mochale, abs(2*x));
else
v.mn += min(mochale, abs(2*x));
}
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 (x < 0)
mv(l, max(x, l.cst - r.cst));
ll y = r.mn - l.cnt*D - l.mn;
if (y > 0)
mv(l, min(y, r.cst - l.cst));
}
if (r.cst < l.cst) {
ll x = l.mx + D - r.mn;
if (x > 0)
mv(r, min(x, l.cst - r.cst));
ll y = l.mx + r.cnt*D - r.mx;
if (y < 0)
mv(r, max(y, r.cst - l.cst));
}
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;
mv(r, x);
mv(l, -x);
t[i].cst += x;
}
t[i].mn = l.mn;
t[i].mx = r.mx;
t[i].cnt = l.cnt + r.cnt;
}
void init(int n) {
sz = n;
fill(t, t+4*sz, __typeof__(*t){ -1, -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, .cnt = 1 };
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); }
}
multiset<ll> S;
bool naive(ll k)
{
ll lst = -1e18;
for (ll x : S) {
ll p = max(x - k, lst + D);
if (p - x > k)
return 0;
lst = p;
}
return 1;
}
ll bin() {
ll l = 0, r = 1e18;
while (l < r) {
ll m = (l+r)/2;
if (naive(m))
r = m;
else
l = m+1;
}
return l;
}
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});
}
srand(time(0));
Loop (i,0,m) {
//b[i]=rand()%100;
cin >> b[i];
//cout << b[i] << ' ';
b[i] *= 2;
cmper.push_back({b[i], i+n});
}
//cout << '\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]);
S.insert(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]);
S.insert(b[i]);
ll x = seg::t[0].cst;
cout << x/2;
if (x%2)
cout << ".5";
cout << ' ';
//cout << double(bin())/2 << '\n';
//cout.flush();
//assert(bin() == x);
}
cout << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
2 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
2 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
278 ms |
41276 KB |
Output is correct |
10 |
Correct |
263 ms |
41368 KB |
Output is correct |
11 |
Correct |
134 ms |
41400 KB |
Output is correct |
12 |
Correct |
167 ms |
41392 KB |
Output is correct |
13 |
Correct |
104 ms |
40844 KB |
Output is correct |
14 |
Correct |
124 ms |
41272 KB |
Output is correct |
15 |
Correct |
230 ms |
40652 KB |
Output is correct |
16 |
Correct |
130 ms |
41364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
159 ms |
40448 KB |
Output is correct |
2 |
Correct |
154 ms |
42552 KB |
Output is correct |
3 |
Correct |
149 ms |
42476 KB |
Output is correct |
4 |
Correct |
130 ms |
40424 KB |
Output is correct |
5 |
Correct |
146 ms |
41640 KB |
Output is correct |
6 |
Correct |
136 ms |
42552 KB |
Output is correct |
7 |
Correct |
141 ms |
43400 KB |
Output is correct |
8 |
Correct |
135 ms |
42148 KB |
Output is correct |
9 |
Correct |
124 ms |
42148 KB |
Output is correct |
10 |
Correct |
151 ms |
44496 KB |
Output is correct |
11 |
Correct |
135 ms |
42992 KB |
Output is correct |
12 |
Correct |
154 ms |
43948 KB |
Output is correct |
13 |
Correct |
126 ms |
42192 KB |
Output is correct |
14 |
Correct |
148 ms |
44112 KB |
Output is correct |
15 |
Correct |
149 ms |
43856 KB |
Output is correct |
16 |
Correct |
123 ms |
41772 KB |
Output is correct |
17 |
Correct |
162 ms |
43440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
159 ms |
40448 KB |
Output is correct |
2 |
Correct |
154 ms |
42552 KB |
Output is correct |
3 |
Correct |
149 ms |
42476 KB |
Output is correct |
4 |
Correct |
130 ms |
40424 KB |
Output is correct |
5 |
Correct |
146 ms |
41640 KB |
Output is correct |
6 |
Correct |
136 ms |
42552 KB |
Output is correct |
7 |
Correct |
141 ms |
43400 KB |
Output is correct |
8 |
Correct |
135 ms |
42148 KB |
Output is correct |
9 |
Correct |
124 ms |
42148 KB |
Output is correct |
10 |
Correct |
151 ms |
44496 KB |
Output is correct |
11 |
Correct |
135 ms |
42992 KB |
Output is correct |
12 |
Correct |
154 ms |
43948 KB |
Output is correct |
13 |
Correct |
126 ms |
42192 KB |
Output is correct |
14 |
Correct |
148 ms |
44112 KB |
Output is correct |
15 |
Correct |
149 ms |
43856 KB |
Output is correct |
16 |
Correct |
123 ms |
41772 KB |
Output is correct |
17 |
Correct |
162 ms |
43440 KB |
Output is correct |
18 |
Correct |
283 ms |
42516 KB |
Output is correct |
19 |
Correct |
311 ms |
44152 KB |
Output is correct |
20 |
Correct |
149 ms |
44292 KB |
Output is correct |
21 |
Correct |
168 ms |
42260 KB |
Output is correct |
22 |
Correct |
241 ms |
42624 KB |
Output is correct |
23 |
Correct |
160 ms |
42376 KB |
Output is correct |
24 |
Correct |
304 ms |
42924 KB |
Output is correct |
25 |
Correct |
142 ms |
42044 KB |
Output is correct |
26 |
Correct |
264 ms |
42072 KB |
Output is correct |
27 |
Correct |
346 ms |
44648 KB |
Output is correct |
28 |
Correct |
215 ms |
42584 KB |
Output is correct |
29 |
Correct |
256 ms |
43956 KB |
Output is correct |
30 |
Correct |
161 ms |
42096 KB |
Output is correct |
31 |
Correct |
191 ms |
44128 KB |
Output is correct |
32 |
Correct |
153 ms |
43876 KB |
Output is correct |
33 |
Correct |
308 ms |
41668 KB |
Output is correct |
34 |
Correct |
184 ms |
43428 KB |
Output is correct |