Submission #487590

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

diversity

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e6;
int n , q , a[N];
int P[N] , p[N];
 main (){
   cin >> n >> q;
   for(int i = 1; i <= n; ++i)cin >> a[i];
   int l , r;
   for(int i = 1; i <= q; ++i)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;
   }
   sort(v.begin() , v.end());
   //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];
      int ok = 1; if(i==sz)ok=0;
      //cout << x << " ";
      //cout << P[sz] - P[i] - (i - 1) * p[sz] << "s"<<endl;
      ans += x * x - x*(x - 1)/2 +  ok*x * ((P[sz] - P[i]) - (i - 1) * (p[sz] - p[i]));
   }
    cout << ans;
}
/// 1 1 2 2 3 4 5 5 5 5

Compilation message (stderr)

diversity.cpp:7:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    7 |  main (){
      |  ^~~~
diversity.cpp: In function 'int main()':
diversity.cpp:21:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |    for(int i =1; i < v.size(); ++i){
      |                  ~~^~~~~~~~~~
diversity.cpp:27:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    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