Submission #826727

#	Time	Username	Problem	Language	Result	Execution time	Memory
826727		NK_	Diversity (CEOI21_diversity)	C++17	64 / 100	2390 ms	44564 KiB

diversity

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
 	
	int N, Q; cin >> N >> Q;
	vi A(N); for(auto& x : A) cin >> x;
	assert(Q == 1);
	int l, r; cin >> l >> r;
	assert(l == 1 && r == N);

	map<int, int> F; for(auto& x : A) F[x]++;

	vpi B; for(auto& x : F) B.pb(mp(x.s, x.f));
	sort(begin(B), end(B));

	vpi L, R;
	for(int i = 0; i < sz(B); i += 2) L.pb(B[i]);
	for(int i = 1; i < sz(B); i += 2) R.pb(B[i]);
	reverse(begin(R), end(R));
	
	vpi ord; 
	for(auto& x : L) ord.pb(x);
	for(auto& x : R) ord.pb(x);

	map<int, int> ORD; for(int i = 0; i < sz(ord); i++) ORD[ord[i].s] = i;

	sort(begin(A), end(A), [&](int x, int y) {
		if (ORD[x] == ORD[y]) return x < y;
		return ORD[x] < ORD[y];
	});

	ll ans = 0;
	map<int, int> lst;
	for(int i = 0; i < N; i++) {
		int LST = (lst.find(A[i]) == lst.end() ? -1 : lst[A[i]]);
		ans += (i - LST) * 1LL * (N - i);
		lst[A[i]] = i;
	}
	cout << ans << nl;

	exit(0-0);
}				

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