Submission #487226

#	Time	Username	Problem	Language	Result	Execution time	Memory
487226		nickmet2004	Diversity (CEOI21_diversity)	C++11	0 / 100	1 ms	204 KiB

diversity

#include<bits/stdc++.h>

using namespace std;
const int N = 3e5 + 5;
int n , q , a[N];
int P[N] , p[N];
int main (){
   cin >> n >> q;
   for(int i = 1; i <= n; ++i)cin >> a[i];
   while(q--){
    int l , r;
    cin >>l >> r;
   }
   sort(a + 1 , a + n + 1);
   vector<int> v{0};
   int k = 1;
   for(int i = 1; i <= n; ++i){
    if(a[i] == a[i + 1])k++;
    else v.emplace_back(k),k=1;
   }
   //for(int x : v)cout << x << " ";cout << endl;
   for(int i =1; i < v.size(); ++i){
    p[i] = p[i - 1] + v[i];
    P[i] = P[i - 1] + v[i] * i;
    //cout << P[i] << " ";
   }
   int sz = v.size() - 1,ans=0;
   for(int i =1; i < v.size(); ++i){
      int x = v[i];
      //cout << x << " ";
      //cout << P[sz] - P[i] - (i - 1) * p[sz] << "s"<<endl;
      ans += x * x - x*(x - 1)/2 +  x * ((P[sz] - P[i]) - (i - 1) * (p[sz] - p[i]));
   }
    cout << ans;
return 0;
}

Compilation message (stderr)

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

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