Submission #70459841

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, c, a[1000005], b[1000005], cnt[1000005], d[2000005], s[2000005], f[1000005], e[1000005];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> c;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	int u = 0;
	for (int i = 0; i < n; ) {
		int j = i;
		while (j < n && a[j] == a[i]) {
			j++;
		}
		b[u] = a[i];
		cnt[u] = j - i;
		u++;
		i = j;
	}
	for (int i = 0; i < u; i++) {
		d[i] = cnt[i];
		d[i + u] = cnt[i];
	}
	s[0] = 0;
	for (int i = 0; i < 2 * u; i++) {
		s[i + 1] = s[i] + d[i];
	}
	for (int k = 0; k <= u; k++) {
		ll t = s[k] + c, l = k + 1, r = 2 * u, j = 2 * u;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (s[mid] >= t) {
				j = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		f[k] = s[j] - s[k];
	}
	e[0] = b[0];
	for (int k = 1; k < u; k++) {
		e[k] = b[k] - b[k - 1];
	}
	e[u] = m - b[u - 1];
	long long ans = 0;
	for (int k = 0; k <= u; k++) {
		ans += e[k] * f[k];
	}
	cout << ans;
	return 0;
}

Submission Info

Judge Result