Submission #652592

#	Time	Username	Problem	Language	Result	Execution time	Memory
652592		rembocoder	Diversity (CEOI21_diversity)	C++17	64 / 100	7026 ms	10692 KiB

diversity

#include <bits/stdc++.h>

#define int int64_t

using namespace std;

const int max_a = 300'000;
const int K = 540;

int32_t main() {
    ios_base::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    vector<vector<pair<int, pair<int, int>>>> gr((n + K - 1) / K);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        gr[l / K].push_back({r, {l, i}});
    }
    vector<int> ans(q);
    for (int i = 0; i < gr.size(); i++) {
        sort(gr[i].begin(), gr[i].end());
        int l = i * K, r = i * K;
        vector<int> fr(max_a);
        vector<int> fr_fr(max_a);
        fr_fr[0] = max_a;
        set<pair<int, int>> s;
        s.insert({0, max_a});

        auto add_a = [&](int x) {
            s.erase({fr[x], fr_fr[fr[x]]});
            fr_fr[fr[x]]--;
            if (fr_fr[fr[x]]) {
                s.insert({fr[x], fr_fr[fr[x]]});
            }
            fr[x]++;
            s.erase({fr[x], fr_fr[fr[x]]});
            fr_fr[fr[x]]++;
            s.insert({fr[x], fr_fr[fr[x]]});
        };

        auto del_a = [&](int x) {
            s.erase({fr[x], fr_fr[fr[x]]});
            fr_fr[fr[x]]--;
            if (fr_fr[fr[x]]) {
                s.insert({fr[x], fr_fr[fr[x]]});
            }
            fr[x]--;
            s.erase({fr[x], fr_fr[fr[x]]});
            fr_fr[fr[x]]++;
            s.insert({fr[x], fr_fr[fr[x]]});
        };

        auto handle_blocks = [&](int L, int k, int l, int n, int& res) {
            res += (k * (n * n + L) - k * l * l - k * (k - 1) * l * L - k * (k - 1) * (2 * k - 1) / 6 * L * L
                    - (n - l) * (n - l) * k + k * (k + 1) * (n - l) * L - k * (k + 1) * (2 * k + 1) / 6 * L * L) / 2;
        };

        for (auto seg: gr[i]) {
            int q_l = seg.second.first, q_r = seg.first, q_i = seg.second.second;
            while (r < q_r) {
                add_a(a[r]);
                r++;
            }
            while (l > q_l) {
                l--;
                add_a(a[l]);
            }
            while (l < q_l) {
                del_a(a[l]);
                l++;
            }
            int res = 0;
            bool last = false; // false = left, true = right
            int total_l = 0, total_r = 0;
            //cerr << endl;
            for (auto tmp: s) {
                int L = tmp.first, total_k = tmp.second;
                if (L == 0) {
                    continue;
                }
                int l_k = total_k / 2 + (total_k % 2 == 1 && last);
                int r_k = total_k / 2 + (total_k % 2 == 1 && !last);
                //cerr << l_k << ' ' << L << endl;
                //cerr << r_k << ' ' << L << endl;
                handle_blocks(L, l_k, total_l, r - l, res);
                handle_blocks(L, r_k, total_r, r - l, res);
                if (total_k % 2 == 1) {
                    last = !last;
                }
                total_l += l_k * L;
                total_r += r_k * L;
            }
            ans[q_i] = res;
        }
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

diversity.cpp: In function 'int32_t main()':
diversity.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::vector<std::pair<long int, std::pair<long int, long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i = 0; i < gr.size(); i++) {
      |                     ~~^~~~~~~~~~~

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