oj.uz

Submission #832086

# Submission time Handle Problem Language Result Execution time Memory
832086 2023-08-20T22:12:16 Z QwertyPi Diversity (CEOI21_diversity) C++14
0 / 100
 0 ms 212 KB 
#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(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

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;
      |         ^

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -