#include<bits/stdc++.h>
using namespace std;
#define vec vector
#define int double
const int INF = 1e17;
struct SegTreeLazy {
vec<int> data;
int n;
SegTreeLazy(int in) {
int n = 1;
while(n<in) n*=2;
data = vec<int>(n);
}
void set(int i, int val) {
data[i] = val;
}
int get(int i) {
return data[i];
}
void upd(int l, int r, int val) {
for(int i = l; i<r; i++) {
data[i] += val;
}
}
};
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, d;
cin >> n >> m >> d;
vec<int> a(n+m+2);
for(int i = 0; i<n+m; i++) {
cin >> a[i];
}
a[n+m] = INF;
a[n+m+1] = -INF;
vec<int> ri(n+m+2);
iota(ri.begin(), ri.end(), 0);
sort(ri.begin(), ri.end(), [&] (int i, int j) { return a[i] < a[j]; });
vec<int> ai(n+m+2);
for(int i = 0; i<n+m+2; i++) {
ai[ri[i]] = i;
}
multiset<int> ms;
ms.insert(0);
ms.insert(n+m+1);
SegTreeLazy left_shift(n+m+2);
SegTreeLazy right_shift(n+m+2);
left_shift.set(0, -INF);
left_shift.set(n+m+1, INF);
right_shift.set(0, -INF);
right_shift.set(n+m+1, INF);
int topt = 0;
for(int i = 0; i<n+m; i++) {
int j = ai[i];
ms.insert(j);
auto it = ms.find(j);
it--;
int prev = *it;
it++; it++;
int nxt = *it;
int l = left_shift.get(prev);
int r = right_shift.get(nxt);
assert(r >= l+d);
int offs = 2*d-(r-l);
if(offs >= 0) {
topt += offs/2;
left_shift.upd(1, j, -offs/2);
right_shift.upd(j+1, n+m+1, offs/2);
r += offs/2;
l -= offs/2;
}
int ml = a[i]-topt;
int mr = a[i]+topt;
int mloffs = (r-d)-ml;
int mroffs = (mr-(l+d));
offs = min(mloffs, mroffs);
// cerr << "----------------" << '\n';
// cerr << "l: " << l << '\n';
// cerr << "r: " << r << '\n';
// cerr << "mloffs: " << mloffs << '\n';
// cerr << "mroffs: " << mroffs << '\n';
if(offs <= 0) {
offs = -offs;
topt += offs/2;
left_shift.upd(1, j, -offs/2);
right_shift.upd(j+1, n+m+1, offs/2);
r += offs/2;
l -= offs/2;
}
int mlpos = max(l+d, a[i]-topt);
int mrpos = min(r-d, a[i]+topt);
left_shift.set(j, mlpos);
right_shift.set(j, mrpos);
int lr = left_shift.get(nxt);
int dist = mlpos+d-lr;
if(dist > 0) {
left_shift.upd(j+1, n+m+1, dist);
}
int rl = right_shift.get(prev);
dist = rl-(mrpos-d);
if(dist > 0) {
right_shift.upd(1, j, -dist);
}
if(i >= n) cout << ((double)((int)(topt*2)))/2 << ' ';
}
cout << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1569 ms |
14596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1569 ms |
14596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
