제출 #724080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
724080		stage	Measures (CEOI22_measures)	C++14	100 / 100	328 ms	33248 KiB

Main

#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){
		cin >> init[i];
		a[i] = {init[i],i};
	}
	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;
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41