Submission #519273

#TimeUsernameProblemLanguageResultExecution timeMemory
519273KeshiDiversity (CEOI21_diversity)C++17
64 / 100
7097 ms6580 KiB
//In the name of God #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; const ll maxn = 3e5 + 100; const ll mod = 1e9 + 7; const ll inf = 1e18; #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout); #define pb push_back #define Mp make_pair #define F first #define S second #define Sz(x) ll((x).size()) #define all(x) (x).begin(), (x).end() ll pw(ll a, ll b){ ll c = 1; while(b){ if(b & 1) c = c * a % mod; a = a * a % mod; b >>= 1; } return c; } int n, q, a[maxn], c[maxn], b[maxn]; int main(){ fast_io; cin >> n >> q; for(int i = 0; i < n; i++){ cin >> a[i]; } while(q--){ int l, r; cin >> l >> r; l--; for(int i = l; i < r; i++){ c[a[i]]++; } vector<int> vec; for(int i = l; i < r; i++){ if(c[a[i]]){ vec.pb(c[a[i]]); c[a[i]] = 0; } } sort(all(vec)); l = 0, r = Sz(vec) - 1; ll s = 0; for(int i = 0; i < Sz(vec); i++){ s += vec[i]; if(i & 1){ b[r--] = vec[i]; } else{ b[l++] = vec[i]; } } ll x = 0, ans = 0; ll m = s; for(int i = 0; i < Sz(vec); i++){ s -= b[i]; ans += m * (m + 1) / 2 - x * (x + 1) / 2 - s * (s + 1) / 2; x += b[i]; } cout << ans << "\n"; } 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...