Submission #832080

#	Time	Username	Problem	Language	Result	Execution time	Memory
832080		QwertyPi	Diversity (CEOI21_diversity)	C++14	64 / 100	205 ms	22560 KiB

diversity

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define int long long
using namespace std;

const int MAXN = 3e5 + 11;
int a[MAXN];
int32_t main(){
    int n, q; cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    map<int, int> c;
    for(int i = 1; i <= n; i++){
        c[a[i]]++;
    }

    vector<int> cnt;
    for(auto [x, y] : c){
        cnt.push_back(y);
    }

    sort(cnt.begin(), cnt.end());

    int ans = 0;
    for(auto x : cnt){
        ans += x * (x + 1) / 2;
    }

    int s1 = 0, s2 = 0;
    for(auto x : cnt){
        s1 += x; s2 += x * x;
    }

    ans += (s1 * s1 - s2) / 2;

    int l = 0, r = 0;
    for(auto x : cnt){
        if(l > r) swap(l, r);
        ans += l * (n - l); l += x;
    }
    ans += l * (n - l);
    cout << ans << endl;
}

Compilation message (stderr)

diversity.cpp: In function 'int32_t main()':
diversity.cpp:20:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |     for(auto [x, y] : c){
      |              ^

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