Submission #1215551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215551		KindaGoodGames	Diversity (CEOI21_diversity)	C++20	0 / 100	1 ms	328 KiB

diversity

#include<bits/stdc++.h>

#define int long long
#define pii pair<int,int>
using namespace std;

int solve(vector<int>& cur){ 
    int sum = 0;
    for(int i = 0; i < cur.size(); i++){
        for(int j = i; j < cur.size(); j++){
            set<int> occ;
            for(int k = i; k <= j; k++){
                occ.insert(cur[k]);
            }
            sum += occ.size();
        }
    }
    return sum;
}


int32_t main() {
    int n,q;
    cin>> n >> q;

    vector<int>arr(n);
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    // construct small-large-small-large... blocks
    while(q--){
        int l,r;
        cin >> l >> r;
        l--;r--;

        vector<int> cur;
        map<int,int> freq;
        for(int i = l; i <= r; i++){ 
            freq[arr[i]]++;
        } 
        vector<pii> temp;
        for(auto p : freq){
            temp.push_back(p);
        }
        sort(temp.begin(),temp.end(), [](pii a, pii b) {
            if(a.second == b.second) return a.first < b.first;
             return a.second < b.second;
            });

        vector<int> cur1;
        int lo = 0, hi = temp.size()-1;
        while(lo <= hi){
            for(int i = 0; i < temp[lo].second; i++){
                cur1.push_back(temp[lo].first);
            }
            lo++;
            if(lo > hi) break;
            for(int i = 0; i < temp[hi].second; i++){
                cur1.push_back(temp[hi].first);
            }
            hi--;
        } 
        vector<int> cur2;
        lo = 0, hi = temp.size()-1;
        while(lo <= hi){
            for(int i = 0; i < temp[hi].second; i++){
                cur2.push_back(temp[hi].first);
            }
            hi--;
            if(lo > hi) break;
            for(int i = 0; i < temp[lo].second; i++){
                cur2.push_back(temp[lo].first);
            }
            lo++;
        } 

        int sum1 = solve(cur1);
        int sum2 = solve(cur2);
        int sum = min(sum1,sum2);
        cout << sum << endl;
    }
}

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