#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int max,min,ans;
};
const int N = 2e5, inf = 1e17;
node segt[4*N+5];
int lazy[4*N+5];
node merge(node a, node b){
node c;
c.ans = max({a.ans,b.ans,a.max-b.min});
c.max = max(a.max,b.max);
c.min = min(a.min,b.min);
return c;
}
void update(int idx, int l, int r, int L, int R, int val){
if (l > R or r < L) return;
if (l >= L and r <= R){
if (L == R) segt[idx] = {val+lazy[idx],val+lazy[idx],0};
else{
segt[idx].max += val;
segt[idx].min += val;
lazy[idx] += val;
}
return;
}
for (int k:{2*idx,2*idx+1}){
segt[k].min += lazy[idx];
segt[k].max += lazy[idx];
lazy[k] += lazy[idx];
}
lazy[idx] = 0;
int mid = (l+r)/2;
update(2*idx,l,mid,L,R,val);
update(2*idx+1,mid+1,r,L,R,val);
segt[idx] = merge(segt[2*idx],segt[2*idx+1]);
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m,d;
cin >> n >> m >> d;
fill_n(segt,4*N+5,node{-inf,inf,-inf});
vector<int> init(n+m), to(n+m);
vector<pair<int,int>> a(n+m);
for (int i=0; i<n+m; ++i){
int pos;
cin >> pos;
a[i] = {pos,i};
init.emplace_back(pos);
}
sort(a.begin(),a.end());
for (int i=0; i<n+m; ++i) to[a[i].second] = i;
for (int i=0; i<n+m; ++i){
int pos = to[i];
update(1,0,n+m+4,pos,pos,init[i]);
update(1,0,n+m+4,pos+1,n+m+4,-d);
if (i >= n){
int ans = segt[1].ans;
cout << ans/2;
if (ans&1) cout << ".5";
cout << ' ';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
33696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
33696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
