Submission #859587

#	Time	Username	Problem	Language	Result	Execution time	Memory
859587		Tenis0206	Diversity (CEOI21_diversity)	C++11	64 / 100	7055 ms	6720 KiB

diversity

#include <bits/stdc++.h>

using namespace std;

const int nmax = 3e5;

int n,q;
int v[nmax + 5];

int fr[nmax + 5];

long long query(int st, int dr)
{
    for(int i=st;i<=dr;i++)
    {
        ++fr[v[i]];
    }
    vector<int> l;
    for(int i=1;i<=nmax;i++)
    {
        if(fr[i] > 0)
        {
            l.push_back(fr[i]);
        }
        fr[i] = 0;
    }
    sort(l.begin(),l.end(),greater<int>());
    deque<int> d;
    for(int i=0;i<l.size();i++)
    {
        if(i % 2 == 0)
        {
            d.push_back(l[i]);
        }
        else
        {
            d.push_front(l[i]);
        }
    }
    int sum_st = 0, sum_dr = dr - st + 1;
    long long rez = 0;
    for(auto it : d)
    {
        sum_dr -= it;
        rez += 1LL * (dr - st + 1) * (dr - st + 2) / 2;
        rez -= 1LL * sum_st * (sum_st + 1) / 2;
        rez -= 1LL * sum_dr * (sum_dr + 1) / 2;
        sum_st += it;
    }
    return rez;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for(int i=1;i<=q;i++)
    {
        int st, dr;
        cin>>st>>dr;
        cout<<query(st,dr)<<'\n';
    }
    return 0;
}

Compilation message (stderr)

diversity.cpp: In function 'long long int query(int, int)':
diversity.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<l.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