제출 #1284473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284473		stefanneagu	Diversity (CEOI21_diversity)	C++20	100 / 100	6120 ms	5564 KiB

diversity

#include <bits/stdc++.h>
#define int long long
// "o mare neintelegere"
// ok lil bro

using namespace std;

const int nmax = 3e5 + 1, qmax = 5e4 + 1, block = sqrt(nmax);

int f[nmax];
int ff[nmax];
unordered_set<int> fff;

void add_ff(int val) {
    // cout << "added " << val << '\n';
    fff.insert(val);
}

void remove_ff(int val) {
    // cout << "removed " << val << '\n';
    fff.erase(val);
}

void add_f(int val) {
    if (f[val] > 0 && ff[f[val]] == 1) {
        remove_ff(f[val]);
    }
    if (f[val] >= 0) {
        ff[f[val]]--;
    }
    f[val]++;
    // cout << "+ " << val << " (" << f[val] << ")\n";
    if (f[val] >= 0) {
        ff[f[val]]++;
    }
    if (f[val] > 0 && ff[f[val]] == 1) {
        add_ff(f[val]);
    }
}

void remove_f(int val) {
    if (f[val] > 0 && ff[f[val]] == 1) {
        remove_ff(f[val]);
    }
    if (f[val] >= 0) {
        ff[f[val]]--;
    }
    f[val]--;
    // cout << "- " << val << " (" << f[val] << ")\n";
    if (f[val] >= 0) {
        ff[f[val]]++;
    }
    if (f[val] > 0 && ff[f[val]] == 1) {
        add_ff(f[val]);
    }
}

int ana(int val, int it, int cnt) {
    return cnt * (it * it * (cnt - 1) * (2 * cnt - 1) + 3 * it * (cnt - 1) * (2 * val + 1) + 6 * val * (val + 1)) / 12;
}

int v[nmax];
int ans[qmax];

struct qry {
    int l, r, i;

    const bool operator < (qry ult) const {
        if (l / block != ult.l / block) {
            return l / block < ult.l / block;
        }
        return r < ult.r;
    }
} Q[qmax];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    for (int i = 1; i <= q; i++) {
        cin >> Q[i].l >> Q[i].r;
        Q[i].i = i;
    }
    sort(Q + 1, Q + q + 1);
    int dr = 0, st = 1;
    for (int i = 1; i <= q; i++) {
        // cout << "!" << Q[i].l << " " << Q[i].r << ": " << '\n';
        while (st <= Q[i].l) {
            remove_f(v[st]);
            st++;
        }
        while (dr >= Q[i].r) {
            remove_f(v[dr]);
            dr--;
        }
        while (st > Q[i].l) {
            st--;
            add_f(v[st]);
        }
        while (dr < Q[i].r) {
            dr++;
            add_f(v[dr]);
        }
        vector<int> vals;
        for (auto it : fff) {
            vals.push_back(it);
        }
        sort(vals.begin(), vals.end());
        int left = 1, right = Q[i].r - Q[i].l + 1;
        int daria = Q[i].r - Q[i].l + 1;
        int cur = 0, sumcnt = 0;
        int cur_l = 0, cur_r = 0;
        // cout << "\t\t" << st << " " << dr << ":\n";
        for (auto it : vals) {
            // cout << "!" << it << " " << ff[it] << '\n';
            int cnt = ff[it];
            sumcnt += cnt;
            if (cnt % 2 == 1) {
                if (left <= daria - right + 1) {
                    cur_l = left;
                    cur_r = cur_l + it - 1;
                    cur += cur_l * (cur_l - 1) / 2;
                    cur += (daria - cur_r) * (daria - cur_r + 1) / 2;
                    left = cur_r + 1;
                } else {
                    cur_r = right;
                    cur_l = cur_r - it + 1;
                    cur += cur_l * (cur_l - 1) / 2;
                    cur += (daria - cur_r) * (daria - cur_r + 1) / 2;
                    right = cur_l - 1;
                }
                cnt--;
            }
            cur += ana(left - 1, it, cnt / 2);
            cur += ana(daria - left - it * (cnt / 2) + 1, it, cnt / 2);
            cur += ana(right - it * (cnt / 2), it, cnt / 2);
            cur += ana(daria - right, it, cnt / 2);
            left += it * cnt / 2;
            right -= it * cnt / 2;
        }
        // cout << '\n';
        // cout << sumcnt << ": " << daria << ", " << cur << '\n';
        ans[Q[i].i] = sumcnt * daria * (daria + 1) / 2 - cur;
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

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