Submission #549564

#	Time	Username	Problem	Language	Result	Execution time	Memory
549564		minhcool	Diversity (CEOI21_diversity)	C++17	64 / 100	90 ms	8968 KiB

diversity

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 4e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, q, a[N];

ii cnt[N];

int cntt[N];

void process(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        cnt[a[i]].fi++;
    }
    for(int i = 1; i <= 300000; i++){
        cntt[cnt[i].fi]++;
        cnt[i].se = i;
    }
    sort(cnt + 1, cnt + 300000 + 1, greater<ii>());
    deque<int> dq;
    vector<ii> vc1, vc2;
    int total = 0;
    for(int i = 1; i <= 300000; i++){
        int temp1 = (cntt[i] + 1) / 2, temp2 = cntt[i] / 2;
        if(!(total & 1)){
            if(temp1) vc1.pb({i, temp1});
            if(temp2) vc2.pb({i, temp2});
        }
        else{
            if(temp2) vc1.pb({i, temp2});
            if(temp1) vc2.pb({i, temp1});
        }
        total += cntt[i];
    }
    for(int i = vc2.size() - 1; i >= 0; i--) vc1.pb(vc2[i]);
    int tol = 0, tol2 = 0, toll = 1;
    /*
    tol: total before, tol2: answer, toll: answer for i
    */
    for(auto it : vc1){
        // 1, 3, 6, 10
        // 1, 2, 5, 6, 11, 12, ...
        // 1, 2, 3, 7, 8, 9, 16, 17, 18, 28, 29, 30, ... 
        // 1, 1, 1, 7, 7, 7, 16, 16, 16, 28, 28, 28, ...
        // 
        /*
        it.se * (it.se + 1) / 2
        tol + 1, tol + 2 * it.fi, tol + 5 * it.fi, ..., tol + 9 * it.fi
        1 + 3 + 6 + 10 + 15 - 5
        1*2/2 + 2*3/2 + 3*4/2 + 4*5/2 + 5*6/2 - 5
        (1*2 + 2*3 + 3*4 + 4*5 + 5*6) / 2 - 5
        ((1*1 + 2*2 + 3*3 + 4*4 + 5*5) + (1+2+3+4+5)) / 2 - 5
        
        */
        int temp = ((it.se * (it.se + 1) * (2 * it.se + 1)) / 6 + (it.se * (it.se + 1)) / 2) / 2 - it.se;
        //cout << temp << "\n";
        temp = temp * it.fi * it.fi + toll * it.fi * it.se;
        //cout << temp << "\n";
        temp += it.se * (it.fi * (it.fi - 1) / 2);
        temp += tol * ((it.se * (it.se - 1)) / 2) * it.fi;
        //cout << temp << "\n";
        toll += ((it.se * (it.se + 1)) / 2) * it.fi + tol * (it.se - 1);
        tol += it.fi * it.se;
        //cout << toll << "\n";
        toll += tol;
        tol2 += temp;
        //cout << it.fi << " " << it.se << "\n";
        //cout << tol << " " << toll << " " << tol2 << "\n";
    }
    cout << tol2 << "\n";
    // 0, 0, 4, 5, 10, 11
    // 1, 2, 5, 6, 11, 12, 19, 20, 29, 30, 41
    // 0, 0, 4, 4, 10, 10
    /*
    tol = toll = tol2 = 0;
    for(int i = 299999; i >= 1; i -= 2){
        tol2 += (cnt[i].fi * (cnt[i].fi + 1)) / 2;
        tol2 += (cnt[i].fi * tol);
        tol += cnt[i].fi;
        toll += cnt[i].fi;
        tol += toll;
    }
    for(int i = 2; i <= 300000; i += 2){
        tol2 += (cnt[i].fi * (cnt[i].fi + 1)) / 2;
        tol2 += (cnt[i].fi * tol);
        tol += cnt[i].fi;
        toll += cnt[i].fi;
        tol += toll;
    }*/
    /*
    for(int i = 1; i <= 300000; i++){
        if(i & 1) for(int j = 1; j <= cnt[i].fi; j++) dq.push_front(cnt[i].se);
        else for(int j = 1; j <= cnt[i].fi; j++) dq.push_back(cnt[i].se);
    }
    int cnt = 0,  lst = -1;
    tol = 0, tol2 = 0;
    //cout << dq.size() << "\n";
    while(dq.size()){
        int u = dq.front();
        //cout << u << "\n";
        dq.pop_front();
        cnt++;
        if(lst != u) tol += cnt;
        else tol++;
        cout << tol << " ";
        tol2 += tol;
        lst = u;
    }
    cout << tol2 << "\n";*/
}

signed main(){
    ios_base::sync_with_stdio(0);
    process();
}

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