Submission #957312

#	Time	Username	Problem	Language	Result	Execution time	Memory
957312		LucaIlie	Diversity (CEOI21_diversity)	C++17	64 / 100	7039 ms	16320 KiB

diversity

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5;
int a[MAX_N + 1];

long long gauss( int n ) {
    return (long long)n * (n + 1) / 2;
}

int main() {
    int n, q;

    cin >> n >> q;
    for ( int i = 1; i <= n; i++ )
        cin >> a[i];

    while ( q-- ) {
        int l, r;
        cin >> l >> r;

        unordered_map<int, int> mp;
        for ( int i = l; i <= r; i++ )
            mp[a[i]]++;

        vector<int> v;
        for ( auto p: mp )
            v.push_back( p.second );

        sort( v.begin(), v.end() );
        vector<int> f( v.size() );
        for ( int i = 0; i < v.size(); i++ ) {
            if ( i % 2 == 0 )
                f[i / 2] = v[i];
            else
                f[v.size() - 1 - i / 2] = v[i];
        }

        int n = r - l + 1;
        long long ans = 0, k = 0;
        for ( int i = 0; i < f.size(); i++ ) {
            ans = ans + gauss( n - k ) - gauss( n - k - f[i] ) + (long long)k * (n - k);
            k += f[i];
        }

        cout << ans << "\n";
    }

    return 0;
}

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:33:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for ( int i = 0; i < v.size(); i++ ) {
      |                          ~~^~~~~~~~~~
diversity.cpp:42:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for ( int i = 0; i < f.size(); i++ ) {
      |                          ~~^~~~~~~~~~

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