Submission #576333

#	Time	Username	Problem	Language	Result	Execution time	Memory
576333		talant117408	Diversity (CEOI21_diversity)	C++17	64 / 100	69 ms	7380 KiB

diversity

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

void solve() {
    int n, q;
    cin >> n >> q;
    vector <int> v(n);
    for (auto &to : v) cin >> to;
    vector <pii> queries(q);
    for (auto &to : queries) cin >> to.first >> to.second;
    for (auto &to : queries) {
        to.first--;
        to.second--;
    }
    sort(all(v));
    if (q == 1) {
        vector <ll> ranges;
        ll cnt = 1;
        for (int i = 1; i < n; i++) {
            if (v[i] == v[i-1]) cnt++;
            else {
                ranges.pb(cnt);
                cnt = 1;
            }
        }
        ranges.pb(cnt);
        sort(rall(ranges));
        ll ans = 0, sum = 0;
        deque <ll> K;
        for (auto to : ranges) {
            if (sz(K)&1) {
                K.push_back(to);
            }
            else {
                K.push_front(to);
            }
        }
        while (sz(K)) {
            auto x = K.front(); K.pop_front();
            ans += x*(x+1)/2 + sum*x + (n-sum-x)*x + sum*(n-sum-x);
            sum += x;
        }
        cout << ans;
    }
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 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