Submission #832088

#TimeUsernameProblemLanguageResultExecution timeMemory
832088QwertyPiDiversity (CEOI21_diversity)C++14
0 / 100
0 ms212 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define int long long using namespace std; const int MAXN = 3e5 + 11; const int MAXQ = 5e4 + 11; const int SQ = 1000; int a[MAXN]; int ans[MAXQ]; int c[MAXN]; int s0, s1, s2; void add(int x){ s0 -= c[x] * (c[x] + 1) / 2; s1 -= c[x]; s2 -= c[x] * c[x]; c[x]++; s0 += c[x] * (c[x] + 1) / 2; s1 += c[x]; s2 += c[x] * c[x]; } void rem(int x){ s0 -= c[x] * (c[x] + 1) / 2; s1 -= c[x]; s2 -= c[x] * c[x]; c[x]--; s0 += c[x] * (c[x] + 1) / 2; s1 += c[x]; s2 += c[x] * c[x]; } struct query{ int l, r, id; }; int32_t main(){ int n, q; cin >> n >> q; for(int i = 0; i < n; i++){ cin >> a[i]; } vector<query> Q; for(int i = 0; i < q; i++){ int l, r; cin >> l >> r; --l; --r; Q.push_back({l, r, i}); } sort(Q.begin(), Q.end(), [](query a, query b){ if(a.l / SQ != b.l / SQ) return a.l / SQ < b.l / SQ; return a.l / SQ % 2 ? a.r > b.r : a.r < b.r; }); map<int, int> c; for(int i = 1; i <= n; i++){ c[a[i]]++; } vector<int> cnt; for(auto [x, y] : c){ cnt.push_back(y); } sort(cnt.begin(), cnt.end()); int l = 0, r = 0; while(r < n) add(a[r++]); int ans = s0 + (s1 * s1 - s2) / 2; int cl = 0, cr = 0; for(auto x : cnt){ if(cl > cr) swap(cl, cr); ans += cl * (n - cl); cl += x; } ans += cl * (n - cl); cout << ans << endl; }

Compilation message (stderr)

diversity.cpp: In function 'int32_t main()':
diversity.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [x, y] : c){
      |              ^
diversity.cpp:65:9: warning: unused variable 'l' [-Wunused-variable]
   65 |     int l = 0, r = 0;
      |         ^
#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...