Submission #999455

#	Time	Username	Problem	Language	Result	Execution time	Memory
999455		mc061	Diversity (CEOI21_diversity)	C++17	100 / 100	2248 ms	6944 KiB

diversity

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#ifndef ONLINE_JUDGE
    // #include "debug.h"
#else
    #define dbg(...) 42
    template<typename T>ostream&operator<<(ostream&os,vector<T>&vec){for(int i=0;i+1<vec.size();++i){os<<vec[i]<<" ";}if(vec.size()>0)os<<vec.back();return os;}
#endif

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

template<typename T>istream&operator>>(istream&is,vector<T>&vec){for(T&element:vec){is>>element;}return is;}
template<typename T>void chmin(T&x,T y){x=min(x,y);}
template<typename T>void chmax(T&x,T y){x=max(x,y);}

const int N = 3e5+6;
const int Qn = 1337;
const int block = 600;
int ar[N];
int qu_lengths[Qn];
int qu_cnt[Qn];
int cnt[N];
int mp[N];
int64_t qAns[N];
bitset<N> bs;

set<int> lengths;

void rem_c(int c) {
    mp[c]--;
    if (mp[c] == 0) bs[c] = 0;
}

void add(int val) {
    if (cnt[val] != 0)
        rem_c(cnt[val]);
    cnt[val]++;
    mp[cnt[val]]++;
    if (mp[cnt[val]] == 1) bs[cnt[val]] = 1;
}

void rem(int val) {
    rem_c(cnt[val]);
    cnt[val]--;
    if (cnt[val] != 0) {
        mp[cnt[val]]++;
        if (mp[cnt[val]] == 1) bs[cnt[val]] = 1;
    }
}

struct segment {
    int length;
    int diffs;
    int64_t ans;
    int64_t ans_left;
    int64_t ans_right;
};

segment merge_two(segment A, segment B) {
    if (A.length == 0) return B;
    if (B.length == 0) return A;
    segment res;
    res.diffs = A.diffs + B.diffs;
    res.length = A.length + B.length;
    res.ans_right = B.ans_right + 1ll*A.ans_right + 1ll*(B.diffs)*A.length;
    res.ans_left = A.ans_left + 1ll*B.ans_left + 1ll*(A.diffs)*B.length;
    res.ans = A.ans + B.ans + 1ll*A.ans_right*B.length + 1ll*B.ans_left*A.length;
    return res;
}

segment form_one(int length, int cnt) {
    segment cur = segment{length, 1, 1ll*length*(length+1)/2, length, length};
    segment res = {0, 0, 0, 0, 0};
    for (; cnt > 0; cnt >>= 1) {
        if (cnt & 1) {
            res = merge_two(res, cur);
        }
        cur = merge_two(cur, cur);
    }
    return res;
}

void go(int ind) {
    vector<int> lengths;
    for (int i = bs._Find_first(); i < bs.size(); i = bs._Find_next(i)) lengths.push_back(i);
    memset(qu_lengths, 0, sizeof(qu_lengths));
    memset(qu_cnt, 0, sizeof(qu_cnt));
    bool odd_to_left = true;
    int ptr = 0;
    for (int le : lengths) {
        int c = mp[le];
        int to_left = c / 2;
        int to_right = c / 2;
        if (c % 2 != 0) {
            if (odd_to_left) {
                to_left++;
            }
            else {
                to_right++;
            }
            odd_to_left ^= 1;
        }
        qu_lengths[ptr] = le;
        qu_lengths[Qn - ptr - 1] = le;
        qu_cnt[ptr] = to_left;
        qu_cnt[Qn - ptr - 1] = to_right;
        ++ptr;
    }
    segment res{0, 0, 0, 0, 0};
    for (int i = 0; i < Qn; ++i) {
        if (qu_cnt[i] == 0) continue;
        segment now = form_one(qu_lengths[i], qu_cnt[i]);
        res = merge_two(res, now);
    }
    qAns[ind] = res.ans;
}

void test_case(signed num) {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> ar[i];
    }
    vector<array<int, 3>> queries;
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        queries.push_back({l, r, i});
    }
    sort(queries.begin(), queries.end(), [&] (const array<int, 3>& a, const array<int, 3>& b) {
        return make_pair(a[0] / block, a[1]) < make_pair(b[0] / block, b[1]); 
    });

    int ql = 0, qr = -1;

    for (int i = 0; i < queries.size(); ++i) {
        while (ql > queries[i][0]) {
            --ql;
            add(ar[ql]);
        }
        while (qr < queries[i][1]) {
            ++qr;
            add(ar[qr]);
        }
        while (ql < queries[i][0]) {
            rem(ar[ql]);
            ++ql;
        }
        while (qr > queries[i][1]) {
            rem(ar[qr]);
            --qr;
        }

        go(queries[i][2]);
    }
    for (int i = 0; i < q; ++i) {
        cout << qAns[i] << "\n";
    }
}

signed main(void) {
    cin.tie(0)->sync_with_stdio(false);

    test_case(69420);
}

Compilation message (stderr)

diversity.cpp: In function 'void go(int)':
diversity.cpp:87:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i = bs._Find_first(); i < bs.size(); i = bs._Find_next(i)) lengths.push_back(i);
      |                                    ~~^~~~~~~~~~~
diversity.cpp: In function 'void test_case(int)':
diversity.cpp:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for (int i = 0; i < queries.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 26 / 26
• Subtask 6: 36 / 36