Submission #1123557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123557		mingga	Diversity (CEOI21_diversity)	C++20	0 / 100	0 ms	324 KiB

diversity

#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
const int mod = 1e9 + 7;
const int inf = 2e18;
const int N = 3e5 + 7;
int n, q, a[N];

struct query {
	int l, r;
} d[N];

namespace sub1 {
	bool check() {
		return q == 1 and d[1].l == 1 and d[1].r == n;
	}
	int cnt[N];
	void solve() {
		for(int i = 1; i <= n; i++) cnt[a[i]]++;
		int mx = * max_element(a + 1, a + n + 1);
		vector<int> vec, suf;
		for(int i = 1; i <= mx; i++) {
			if(cnt[i] > 0) {
				vec.pb(cnt[i]);
			}
		}
		suf.resize(sz(vec), 0);
		suf[sz(suf) - 1] = vec[sz(suf) - 1];
		int cur = sz(suf) * suf.back();
		for(int i = sz(suf) - 2; i >= 0; i--) {
			suf[i] = suf[i + 1] + vec[i];
			cur += vec[i] * (i + 1);
		}
		int ans = 0;
		// cout << cur << ln;
		for(int i = 0; i < sz(suf); i++) {
			ans += vec[i] * cur;
			cur -= suf[i];
		}
		cout << ans << ln;
	}
}


signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	cin >> n >> q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= q; i++) {
		int l, r; cin >> l >> r;
		d[i] = {l, r};
	}
	if(sub1::check()) sub1::solve();
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 26
• Subtask 6: 0 / 36