oj.uz

Submission #487593

# Submission time Handle Problem Language Result Execution time Memory
487593 2021-11-16T09:17:48 Z nickmet2004 Diversity (CEOI21_diversity) C++11
0 / 100
 1 ms 204 KB 
#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;
   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()); v.emplace_back(0); reverse(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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -