Submission #1214021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214021		Tob	Measures (CEOI22_measures)	C++20	100 / 100	205 ms	31032 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;
typedef array <ll, 4> ar;

const int ofs = (1 << 18);

int n, m, d;
int a[ofs], b[ofs], c[ofs];
ar t[2*ofs];

ar mer(ar x, ar y) {
	ar z;
	z[0] = max(max(x[0], y[0]), x[2]+y[1]);
	z[1] = max(x[1], x[3]+y[1]);
	z[2] = max(y[2], y[3]+x[2]);
	z[3] = x[3]+y[3];
	return z;
}

void add(int x, ll y) {
	x += ofs;
	t[x] = {max(0LL, y), max(0LL, y), max(0LL, y), y};
	while (x /= 2) t[x] = mer(t[2*x], t[2*x+1]);
}

int main () {
	FIO;
	cin >> n >> m >> d;
	vector <pii> v;
	for (int i = 0; i < n+m; i++) cin >> a[i], v.pb({a[i], i});
	sort(all(v));
	for (int i = 0; i < n+m; i++) b[v[i].S] = i, c[i] = v[i].F;
	
	set <int> s;
	for (int i = 0; i < n+m; i++) {
		auto p = s.lower_bound(b[i]);
		if (!i);
		else if (p == s.begin()) add(*p, d-c[*p]+a[i]);
		else if (p == s.end()) add(b[i], d-a[i]+c[*(--p)]);
		else {
			int z = *p;
			int y = *(--p);
			add(b[i], d-a[i]+c[y]);
			add(z, d-c[z]+a[i]);
		}
		s.insert(b[i]);
		if (i >= n) {
			cout << t[1][0]/2;
			if (t[1][0]%2) cout << ".5";
			cout << " ";
		}
	}

	return 0;
}

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