Submission #495601

#TimeUsernameProblemLanguageResultExecution timeMemory
495601VictorDiversity (CEOI21_diversity)C++17
64 / 100
110 ms14124 KiB
// #pragma GCC target ("avx,avx2,fma") // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast // #pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define per(i, a, b) for (int i = (b - 1); i >= (a); --i) #define trav(a, x) for (auto &a : x) #define all(x) x.begin(), x.end() #define sz(x) x.size() #define pb push_back #define debug(x) cout << #x << " = " << x << endl #define umap unordered_map #define uset unordered_set typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; const int INF = 1'000'000'007; int n, arr[300001], q; int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); umap<int, int> ttoi; vii types; cin >> n >> q; rep(i, 0, n) { int type; cin >> type; if (!ttoi.count(type)) { types.emplace_back(0, sz(ttoi)); ttoi[type] = sz(types) - 1; } ++types[ttoi[type]].first; } sort(all(types)); n = sz(types); int lo = 0, hi = n - 1; bool side = 0; ll ans = 0; trav(item, types) { int type, cnt; tie(cnt, type) = item; if (side) arr[hi--] = cnt; else arr[lo++] = cnt; side ^= 1; ans += ll(cnt) * (cnt + 1) / 2; } if (q == 1) { ll prefix=0,fac=0; rep(i, 0, n){ ans+=arr[i]*fac; prefix+=arr[i]; fac+=prefix+arr[i]; } cout << ans << endl; } return 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...