Submission #709019

#TimeUsernameProblemLanguageResultExecution timeMemory
709019Sanzhar23Diversity (CEOI21_diversity)C++14
64 / 100
72 ms12128 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define bug cout << "bug" << endl #define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define all(x) x.begin(), x.end() #define F first #define S second #define pll pair <ll, ll> #define pii pair <int, int> #define triple pair <pair <ll, ll> , ll> #define ull unsigned long long #define ld long double #define pinode pair <node*, node*> const ll INF = 9e18 + 5; const ll inf = 1e9 + 5; const ll N = 3e5 + 5; const ll shift = 2e6; const ll mod = 998244353; const ll mod2 = 1e9 + 9; const ll M = 1e3 + 5; const ll LOG = 21; const ll sp = 263; const ll sp2 = 9973; const int block = 100; const double eps = 1e-10; int n, q; int a[N], cnt[N], pref[N], suf[N]; int main(){ speed; cin >> n >> q; for(int i = 1; i <= n; i++){ cin >> a[i]; cnt[a[i]]++; } int l, r; cin >> l >> r; vector <pii> vt; for(int i = 1; i <= 300000; i++){ if(cnt[i] != 0) vt.pb({cnt[i], i}); } sort(all(vt)); vector <int> nw; vector <pii> gt; gt.pb({0, 0}); for(int i = 0; i < vt.size(); i++){ int x = vt[i].S, col = vt[i].F; if(i % 2 == 0){ gt.pb({x, col}); for(int j = 0; j < col; j++){ nw.pb(x); } } } for(int i = vt.size() - 1; i >= 0; i--){ int x = vt[i].S, col = vt[i].F; if(i % 2 == 1){ gt.pb({x, col}); for(int j = 0; j < col; j++){ nw.pb(x); } } } ll ans = 0; /* for(int i = 0; i < nw.size(); i++){ set <int> st; for(int j = i; j < nw.size(); j++){ st.insert(nw[j]); ans += (int) st.size(); } } */ int len = gt.size() - 1; for(int i = 1; i <= len; i++){ pref[i] = pref[i - 1] + gt[i].S; } for(int i = len; i >= 1; i--){ suf[i] = suf[i + 1] + gt[i].S; } for(int i = 1; i <= len; i++){ int x = gt[i].F, col = gt[i].S; ll f1 = pref[i - 1] * 1ll * suf[i + 1]; ll f2 = col * 1ll * (col + 1) / 2ll; ll f3 = col * 1ll * pref[i - 1]; ll f4 = col * 1ll * suf[i + 1]; ans += (f1 + f2 + f3 + f4); } cout << ans << endl; } /* %I64d6 %I64d */

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i = 0; i < vt.size(); i++){
      |                 ~~^~~~~~~~~~~
diversity.cpp:89:7: warning: unused variable 'x' [-Wunused-variable]
   89 |   int x = gt[i].F, col = gt[i].S;
      |       ^
#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...