제출 #946719

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
946719		MinaRagy06	Measures (CEOI22_measures)	C++17	100 / 100	486 ms	23748 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define md ((l + r) >> 1)
#define SZ(x) (int) x.size()

struct node {
	ll pos, neg, lazy;
	int cnt;
	node(ll x) {
		pos = x;
		neg = -x;
		cnt = 1;
		lazy = 0;
	}
	node() {pos = neg = -1e18; cnt = lazy = 0;}
	friend node operator+(const node &l, const node &r) {
		node ret;
		ret.pos = max(l.pos, r.pos);
		ret.neg = max(l.neg, r.neg);
		ret.cnt = l.cnt + r.cnt;
		return ret;
	}
} seg[1 << 19];
void process(int i, int l, int r) {
	if (l != r) {
		for (auto c : {i << 1, i << 1 | 1}) {
			seg[c].lazy += seg[i].lazy;
		}
	}
	seg[i].pos += seg[i].lazy;
	seg[i].neg -= seg[i].lazy;
	seg[i].lazy = 0;
}
void add(int i, int l, int r, int s, int e, ll v) {
	process(i, l, r);
	if (s <= l && r <= e) {
		seg[i].lazy += v;
		process(i, l, r);
		return;
	}
	if (r < s || e < l) {
		return;
	}
	add(i << 1, l, md, s, e, v);
	add(i << 1 | 1, md + 1, r, s, e, v);
	seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
ll mx = -1e18;
ll d;
void upd(int i, int l, int r, int x, ll v, ll pos) {
	process(i, l, r);
	if (r < x || x < l) {
		return;
	}
	if (l == r) {
		seg[i].pos = max(seg[i].pos, d * pos - v);
		seg[i].neg = max(seg[i].neg, -(d * pos - v));
		mx = max(mx, seg[i].pos + seg[i].neg);
		seg[i].cnt++;
		return;
	}
	upd(i << 1, l, md, x, v, pos);
	upd(i << 1 | 1, md + 1, r, x, v, pos + seg[i << 1].cnt);
	seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
node get(int i, int l, int r, int s, int e) {
	process(i, l, r);
	if (s <= l && r <= e) {
		return seg[i];
	}
	if (r < s || e < l) {
		return node();
	}
	return get(i << 1, l, md, s, e) + get(i << 1 | 1, md + 1, r, s, e);
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, m;
	cin >> n >> m >> d;
	int a[n], b[m];
	vector<int> v;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		v.push_back(a[i]);
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
		v.push_back(b[i]);
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	auto insert = [&] (int x) {
		int pos = lower_bound(v.begin(), v.end(), x) - v.begin();
		add(1, 0, v.size() - 1, pos, v.size() - 1, d);
		upd(1, 0, v.size() - 1, pos, x, 0);
		ll l = get(1, 0, v.size() - 1, 0, pos - 1).neg;
		ll r = get(1, 0, v.size() - 1, pos, v.size() - 1).pos;
		mx = max(mx, l + r);
		l = get(1, 0, v.size() - 1, 0, pos).neg;
		r = get(1, 0, v.size() - 1, pos + 1, v.size() - 1).pos;
		mx = max(mx, l + r);
		return mx;
	};
	for (int i = 0; i < n; i++) {
		mx = max(mx, insert(a[i]));
	}
	for (int i = 0; i < m; i++) {
		mx = max(mx, insert(b[i]));
		ll v = max(mx, 0ll);
		if (v & 1) {
			cout << v / 2 << ".5 ";
		} else {
			cout << v / 2 << ' ';
		}
	}
	cout << '\n';
	return 0;
}

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