제출 #1284461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284461		stefanneagu	Diversity (CEOI21_diversity)	C++20	64 / 100	29 ms	4764 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 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++) {
        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]);
        }
        // cout << "!" << Q[i].l << " " << Q[i].r << ": " << '\n';
        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 (st <= daria - dr + 1) {
                    cur_l = st;
                    cur_r = cur_l + it - 1;
                    cur += cur_l * (cur_l - 1) / 2;
                    cur += (daria - cur_r) * (daria - cur_r + 1) / 2;
                    // cout << "1s " << cur_l << " " << cur_r << ": " << daria * (daria + 1) / 2 - cur_l * (cur_l - 1) / 2 - (daria - cur_r) * (daria - cur_r + 1) / 2 << '\n';
                    st = cur_r + 1;
                } else {
                    cur_r = dr;
                    cur_l = cur_r - it + 1;
                    cur += cur_l * (cur_l - 1) / 2;
                    cur += (daria - cur_r) * (daria - cur_r + 1) / 2;
                    // cout << "2s " << cur_l << " " << cur_r << ": " << daria * (daria + 1) / 2 - cur_l * (cur_l - 1) / 2 - (daria - cur_r) * (daria - cur_r + 1) / 2 << '\n';
                    dr = cur_l - 1;
                }
                cnt--;
            }
            int val;
            // st - 1
            val = st - 1;
            for (int coef = 0; coef < cnt / 2; coef++) {
                cur += (val + it * coef) * (val + it * coef + 1) / 2;
            }
            val = daria - st - it * (cnt / 2) + 1;
            for (int coef = 0; coef < cnt / 2; coef++) {
                cur += (val + it * coef) * (val + it * coef + 1) / 2;
            }
            /*
            for (int coef = 0; coef < cnt / 2; coef++) {
                cur += (val + it * coef) * (val + it * coef + 1) / 2;
            }
            for (int coef = 0; coef < cnt / 2; coef++) {
                cur += (val + it * coef) * (val + it * coef + 1) / 2;
            }
            */
            while (cnt) {
                cur_l = st;
                cur_r = cur_l + it - 1;
                // cur += cur_l * (cur_l - 1) / 2;
                // cur += (daria - cur_r) * (daria - cur_r + 1) / 2;
                // cout << cur_l << " " << cur_r << ": " << daria * (daria + 1) / 2 - cur_l * (cur_l - 1) / 2 - (daria - cur_r) * (daria - cur_r + 1) / 2 << '\n';
                cur_r = dr;
                cur_l = cur_r - it + 1;
                cur += cur_l * (cur_l - 1) / 2;
                cur += (daria - cur_r) * (daria - cur_r + 1) / 2;
                // cout << cur_l << " " << cur_r << ": " << daria * (daria + 1) / 2 - cur_l * (cur_l - 1) / 2 - (daria - cur_r) * (daria - cur_r + 1) / 2 << '\n';
                st += it, dr -= 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: 0 / 36