题解：P9000 [CEOI 2022] Measures

/*

		2025.11.10

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair<int,int>P;
const int MAXN=1000005,inf=0x3f3f3f3f3f3f3f3f;
int n,m,D,rev[MAXN];
P a[MAXN];
struct node{
	int l,r,mn,mx,ans,d;
}tree[MAXN*4];
void up(int x){
	tree[x].mx=max(tree[x*2].mx,tree[x*2+1].mx);
	tree[x].mn=min(tree[x*2].mn,tree[x*2+1].mn);
	tree[x].ans=max(max(tree[x*2].ans,tree[x*2+1].ans),tree[x*2+1].mx-tree[x*2].mn);
}
void build(int x,int l,int r){
	tree[x].l=l,tree[x].r=r;
	if(l==r){
		tree[x].mn=inf,tree[x].mx=-inf,tree[x].ans=0;
		return ;
	}
	int mid=(l+r)>>1;
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
	up(x);
}
void down(int x){
	int &t=tree[x].d;
	tree[x*2].mn+=t,tree[x*2].mx+=t,tree[x*2].d+=t;
	tree[x*2+1].mn+=t,tree[x*2+1].mx+=t,tree[x*2+1].d+=t;
	t=0;
}
void add(int x,int l,int r,int t){
	if(tree[x].l>=l&&tree[x].r<=r){
		tree[x].mn+=t,tree[x].mx+=t,tree[x].d+=t;
		return ;
	}
	if(tree[x].d)down(x);
	int mid=(tree[x].l+tree[x].r)>>1;
	if(l<=mid)add(x*2,l,r,t);
	if(r>mid)add(x*2+1,l,r,t);
	up(x);
}
void change(int x,int l,int t){
	if(tree[x].l==tree[x].r){
		tree[x].mx=tree[x].mn=tree[x].mn-inf-t;
		return ;
	}
	if(tree[x].d)down(x);
	int mid=(tree[x].l+tree[x].r)>>1;
	if(l<=mid)change(x*2,l,t);
	else change(x*2+1,l,t);
	up(x);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>m>>D;
    for(int i=1;i<=n;i++)cin>>a[i].fi,a[i].se=i;
    for(int i=1;i<=m;i++)cin>>a[i+n].fi,a[i+n].se=i+n;
    sort(a+1,a+1+n+m);
    for(int i=1;i<=n+m;i++)rev[a[i].se]=i;
    build(1,1,n+m);
    for(int i=1;i<=n;i++){
    	int t=rev[i];
    	if(t<n+m)add(1,t+1,n+m,D);
    	change(1,t,a[t].fi);
	}
	for(int i=n+1;i<=n+m;i++){
		int t=rev[i];
		if(t<n+m)add(1,t+1,n+m,D);
    	change(1,t,a[t].fi);
    	if(tree[1].ans%2)cout<<tree[1].ans/2<<".5 ";
    	else cout<<tree[1].ans/2<<" ";
	}
    return 0;
}