# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1103434 | ro9669 | Diversity (CEOI21_diversity) | C++17 | 7044 ms | 6008 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;
typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;
const int maxN = int(3e5)+7;
int n , q , a[maxN] , cnt[maxN] , sum[2];
void solve(){
cin >> n >> q;
for (int i = 1 ; i <= n ; i++) cin >> a[i];
while (q--){
int l , r;
cin >> l >> r;
for (int i = 1 ; i < maxN ; i++) cnt[i] = 0;
for (int i = l ; i <= r ; i++) cnt[a[i]]++;
vector<int> p;
for (int i = 1 ; i < maxN ; i++){
if (cnt[i] > 0) p.push_back(cnt[i]);
}
sort(all(p));
ll ans = 0;
sum[0] = sum[1] = 0;
for (int i = 0 ; i < sz(p) ; i++){
ans += 1ll * p[i] * (p[i] + 1) / 2;
if (i % 2 == 0){
int x = sum[0] , y = (r - l + 1) - sum[0] - p[i];
ans += 1ll * x * y;
ans += 1ll * (x + y) * p[i];
}
else{
int x = sum[1] , y = (r - l + 1) - sum[1] - p[i];
ans += 1ll * x * y;
ans += 1ll * (x + y) * p[i];
}
sum[i % 2] += p[i];
}
cout << ans << "\n";
}
}
#define name "A"
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(name".INP" , "r")){
freopen(name".INP" , "r" , stdin);
freopen(name".OUT" , "w" , stdout);
}
int t = 1; //cin >> t;
while (t--) solve();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |