Submission #1302390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302390		tkm_algorithms	Diversity (CEOI21_diversity)	C++20	38 / 100	156 ms	9864 KiB

diversity

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using P = pair<int, int>;
#define int ll
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 1e9+7;

void solve() {
	int n, q; cin >> n >> q;
	//rep(i, 0, n)
	map<int, int> mp;
	rep(i, 0, n) {
		int x; cin >> x; 
		mp[x] += 1;
	}
	vector<int> a;
	for (auto i: mp)a.push_back(i.second);
	sort(all(a));
	vector<int> res;
	rep(i, 0, sz(a))
		if (i%2==0)res.push_back(a[i]);
	
	for (int i = sz(a)-1; i >= 0; --i)
		if (i&1)res.push_back(a[i]);
		
	//segtree st;
	//st.build(res);
		
	int ans = 0;
	for (auto i: res)
		ans += i*(i+1)/2;
		
	int l, r; cin >> l >> r;
	
	int m = sz(res);
	vector<int> p(m+3), p2(m+3);
	
	rep(i, 0, m)
		p[i] = i*res[i]+(i>0?p[i-1]:0),
		p2[i] = res[i]+(i>0?p2[i-1]:0);
	p[m] = p[m-1], p2[m] = p2[m-1];
	
	//cout << st.get(2, 3).second << nl;
	//for (auto i: res)cout << i << " ";
	//cout << nl;
	
	rep(i, 0, sz(res)) {
		P g = P(p[m]-p[i]+p2[m]-p2[i], p2[m]-p2[i]);
		int x = (g.first-g.second*i)*res[i];
		//assert(ans <= (ll)1e18);
		int y = 0;
		rep(j, i+1, sz(res))y += (res[j]*j+res[j]-res[j]*i)*res[i];
		ans += x;
		assert(x==y);
		//if (x != y) {
			//cout << g.second << " " << nl;
			//cout << i << " " << x << " " << y << nl;
		//}
	}
		
	cout << ans << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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