Submission #957312

#TimeUsernameProblemLanguageResultExecution timeMemory
957312LucaIlieDiversity (CEOI21_diversity)C++17
64 / 100
7039 ms16320 KiB
#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++ ) {
      |                          ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...