Submission #995596

#	Time	Username	Problem	Language	Result	Execution time	Memory
995596		asdasdqwer	Diversity (CEOI21_diversity)	C++14	64 / 100	244 ms	46160 KiB

diversity

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

#define int int64_t
#define pii array<int,2>

struct Segtree {
    vector<int> seg, lz;
    int n;
    Segtree(int sz) {
        n=1;
        while (n<sz)n*=2;
        seg.assign(2*n,0);
        lz.assign(2*n,0);
    }

    void pushdown(int x, int l) {
        if (lz[x] == 0) return;
        lz[2*x+1] += lz[x];
        lz[2*x+2] += lz[x];
        seg[2*x+1] += (l/2) * lz[x];
        seg[2*x+2] += (l/2) * lz[x];
        lz[x]=0;
    }

    void inc(int l, int r, int v, int x, int lx, int rx) {
        if (lx >= r || rx <= l) return;
        if (lx >= l && rx <= r) {
            seg[x] += (rx-lx) * v;
            lz[x] += v;
            return;
        }

        pushdown(x, rx-lx);

        int m=(lx+rx)/2;
        inc(l, r, v, 2*x+1, lx, m);
        inc(l, r, v, 2*x+2, m, rx);
        seg[x] = seg[2*x+1] + seg[2*x+2];
    }

    void inc(int l, int r, int v) {
        inc(l, r, v, 0, 0, n);
    }

    int get(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l) return 0;
        if (lx >= l && rx <= r) {
            return seg[x];
        }

        pushdown(x, rx-lx);

        int m=(lx+rx)/2;
        return get(l, r, 2*x+1, lx, m) + get(l, r, 2*x+2, m, rx);
    }

    int get(int l, int r) {
        return get(l, r, 0, 0, n);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n,q;cin>>n>>q;
    vector<int> a(n);
    for (int &x:a)cin>>x;
    sort(a.begin(), a.end());

    vector<int> b = a;
    b.erase(unique(b.begin(), b.end()), b.end());

    // coordinate compression
    map<int,int> mp;
    for (int i=0;i<(int)b.size();i++) {
        mp[b[i]]=i;
    }

    for (int &x:a) {
        x = mp[x];
    }

    vector<int> cnt(b.size());

    for (int i=0;i<n;i++) {
        cnt[a[i]]++;
    }

    sort(cnt.begin(), cnt.end());

    vector<int> newarr(n);
    deque<int> idx;
    for (int i=0;i<n;i++) idx.push_back(i);

    for (int i=0;i<(int)cnt.size();i++) {
        if (i % 2 == 0) {
            for (int j=0;j<cnt[i];j++) {
                int id = idx.back();idx.pop_back();
                newarr[id] = i;
            }
        }

        else {
            for (int j=0;j<cnt[i];j++) {
                int id = idx.front();idx.pop_front();
                newarr[id] = i;
            }
        }
    }

    int res = n;
    Segtree sg(n);
    for (int i=0;i<n;i++) {
        if (i != 0 && newarr[i] != newarr[i-1]) {
            sg.inc(0, i, 1);
        }

        res += sg.seg[0];
        sg.inc(i, i+1, 1);
    }

    cout<<res<<"\n";
}

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