Submission #1219598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219598		MateiKing80	Measures (CEOI22_measures)	C++20	100 / 100	463 ms	48236 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

using pii = pair<int, int>;
#define fr first
#define sc second

const int inf = 1e16;
int d;

const int N = 2e5 + 15;

struct ura {
	int l = 0, r = 0, ans = 0, cnt = 0;
} aint[4 * N];

ura nou(int v, int c) {
	ura a;
	a.cnt = c;
	a.ans = d * (c - 1);
	a.l = v + d * (c - 1);
	a.r = -v + d * c;
	return a;
}

ura operator +(ura x, ura y) {
	if (x.cnt == 0)
		return y;
	if (y.cnt == 0)
		return x;
	ura aux;
	aux.ans = max(max(x.ans, y.ans), x.l + y.r);
	aux.cnt = x.cnt + y.cnt;
	aux.l = max(y.l, x.l + d * y.cnt);
	aux.r = max(x.r, y.r + d * x.cnt);
	return aux;
}

void update(int pos, int st, int dr, int loc, ura val) {
	if (st == dr) {
		aint[pos] = val;
		return;
	}
	int mid = (st + dr) >> 1;
	if (loc <= mid)
		update(2 * pos, st, mid, loc, val);
	else
		update(2 * pos + 1, mid + 1, dr, loc, val);
	aint[pos] = aint[2 * pos] + aint[2 * pos + 1];
}

signed main() {
	int n, m;
	cin >> n >> m >> d;
	swap(m, n);
	n += m;
	map<int, int> f, norm;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		f[a[i]] ++;
	}
	int nrm = 0;
	for (auto i : f)
		norm[i.fr] = ++ nrm;
	vector<int> fr(n + 1);
	for (int i = 1; i <= n; i ++) {
		fr[norm[a[i]]] ++;
		update(1, 1, nrm, norm[a[i]], nou(a[i], fr[norm[a[i]]]));
		if (i > m) {
			int ans = max(0ll, aint[1].ans);
			cout << ans / 2;
			if (ans % 2 == 1)
				cout << ".5";
			cout << " ";
		}
	}
	cout << '\n';
}

/*
ans = max(i<j)(1/2*((j - i) * d - (aj - ai)));
cred
*/

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