제출 #1283102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283102		GoBananas69	Diversity (CEOI21_diversity)	C++20	38 / 100	14 ms	1756 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    if (!(cin >> N >> Q)) return 0;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    while (Q--) {
        int L, R;
        cin >> L >> R;
        --L; --R;
        // frequency for values 1..1000
        const int MAXV = 1000;
        vector<int> freq(MAXV + 1, 0);
        for (int i = L; i <= R; ++i) ++freq[A[i]];

        // collect block sizes (non-zero frequencies)
        vector<int> blocks;
        for (int v = 1; v <= MAXV; ++v) if (freq[v] > 0) blocks.push_back(freq[v]);
        if (blocks.empty()) {
            cout << 0 << '\n';
            continue;
        }

        sort(blocks.begin(), blocks.end(), greater<int>());

        deque<int> dq;
        bool putLeft = true;
        for (int s : blocks) {
            if (putLeft) dq.push_front(s);
            else       dq.push_back(s);
            putLeft = !putLeft;
        }

        int m = 0;
        for (int s : blocks) m += s;
        ll T = 1LL * m * (m + 1) / 2;
        ll ans = 0;
        int P = 0;
        for (int s : dq) {
            ll left_len = P;
            ll right_len = m - (P + s);
            ll left_sub = left_len * (left_len + 1) / 2;
            ll right_sub = right_len * (right_len + 1) / 2;
            ll intersect = T - left_sub - right_sub; // number of subarrays that include this value
            ans += intersect;
            P += s;
        }

        cout << ans << '\n';
    }
    return 0;
}

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