Submission #1122215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122215		peacebringer1667	Diversity (CEOI21_diversity)	C++17	64 / 100	68 ms	5580 KiB

diversity

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define db double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 3e5 + 5;

inline ll SPQR(ll x){
	return x * (x + 1)/2;
}

int a[maxn];
pir Q[maxn];

void input(int n,int q){
	for (int i = 1 ; i <= n ; i++) cin >> a[i];
	for (int i = 1 ; i <= q ; i++)
	  cin >> Q[i].fi >> Q[i].se;
}

namespace subtask_1_5{
	bool subtask_1_5(int n,int q){
		if (q > 1) return 0;
		if (Q[1].fi != 1 || Q[1].se != n) return 0;
		return 1;
	}
	
	vector <int> occ;
	
	void gen_occurences(int n){
		int cnt = 0;
		sort(a + 1,a + 1 + n);
		
		for (int i = 1 ; i <= n ; i++){
			cnt++;
			
			if (a[i] != a[i + 1]) occ.push_back(cnt),cnt = 0;
		}
	}
	
	ll get_cost(int n){
		ll cost = SPQR(n) - (ll)occ.size() * (ll)(n + 1);
		
		deque <int> dq;
		int id = 0;
		sort(occ.begin(),occ.end());
		
		for (int i = 0 ; i < occ.size() ; i += 2)
		  dq.push_back(occ[i]);
		for (int i = occ.size() - 1 - (occ.size() % 2) ; i >= 0 ; i -= 2)
		  dq.push_back(occ[i]);
		
		int x = 1;
		while (dq.size()){
			cost += (ll)x * (ll)(n + 2 - x);
			
			x += dq.front();
			dq.pop_front();
		}
		
		return cost;
	}
	
	ll solve(int n,int q){
		gen_occurences(n);
		
		return get_cost(n);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
//	freopen("DIVERSITY.inp","r",stdin);
//	freopen("DIVERSITY.out","w",stdout);
	
	int n,q;
	cin >> n >> q;
	input(n,q);
	
	cout << subtask_1_5::solve(n,q);

	return 0;
}

Compilation message (stderr)

diversity.cpp: In function 'long long int subtask_1_5::get_cost(int)':
diversity.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (int i = 0 ; i < occ.size() ; i += 2)
      |                    ~~^~~~~~~~~~~~
diversity.cpp:50:7: warning: unused variable 'id' [-Wunused-variable]
   50 |   int id = 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