Submission #576841

#	Time	Username	Problem	Language	Result	Execution time	Memory
576841		talant117408	Diversity (CEOI21_diversity)	C++17	64 / 100	7003 ms	4640 KiB

diversity

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int MAXN = 3e5+7;

ll calc(ll n) {
    return n*(n+1)/2;
}

ll calc2(ll n) {
    return n*(n+1)*(2*n+1)/6;
}

struct MO {
    vector <int> freq;
    set <pii> comp;
    int N;
    
    MO() {
        N = 0;
        freq.resize(MAXN);
    }
    void add(int n) {
        auto it = comp.lb(mp(freq[n], 0));
        pii a;
        if (it != comp.end() && (*it).first == freq[n]) {
            a = *it;
            comp.erase(it);
            if (a.second > 1) {
                comp.insert(mp(a.first, a.second-1));
            }
        }
        
        it = comp.lb(mp(freq[n]+1, 0));
        if (it == comp.end() || (*it).first != freq[n]+1) {
            comp.insert(mp(freq[n]+1, 1));
        }
        else {
            a = *it;
            comp.erase(it);
            a.second++;
            comp.insert(a);
        }
        freq[n]++;
        N++;
    }
    void remove(int n) {
        auto it = comp.lb(mp(freq[n], 0));
        pii a;
        if (it != comp.end() && (*it).first == freq[n]) {
            a = *it;
            comp.erase(it);
            if (a.second > 1) {
                comp.insert(mp(a.first, a.second-1));
            }
        }
        
        if (freq[n] > 1) {
            it = comp.lb(mp(freq[n]-1, 0));
            if (it == comp.end() || (*it).first != freq[n]-1) {
                comp.insert(mp(freq[n]-1, 1));
            }
            else {
                a = *it;
                comp.erase(it);
                a.second++;
                comp.insert(a);
            }
        }
        freq[n]--;
        N--;
    }
    ll get() {
        int saizu = 0;  
        deque <pll> K;
        set <pii> :: reverse_iterator rit;
        for (rit = comp.rbegin(); rit != comp.rend(); rit++) {
            auto x = *rit;
            if (saizu % 2 == 0) {
                K.push_front(mp(x.first, (x.second+1)/2));
                if (x.second > 1)
                    K.push_back(mp(x.first, x.second/2));
            }
            else {
                if (x.second > 1) 
                    K.push_front(mp(x.first, x.second/2));
                K.push_back(mp(x.first, (x.second+1)/2));
            }
            saizu += x.second;
        }
        ll l = 0, r;
        ll ans = 0;
        for (auto p : K) {
            ll x = p.first, k = p.second;
            r = N-l-x;
            ll a = k*calc(x);
            ll b = k*l + x*calc(k-1);
            ll c = k*r - x*calc(k-1);
            ll d = k*l*r + x*(r*calc(k-1) - l*calc(k-1) - x*calc2(k-1));
            ans += a + b*x + c*x + d;
            l += k*x;
        }
        return ans;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector <int> v(n);
    vector <ll> ans(q);
    vector <pair <pii, int>> queries(q);
    for (auto &to : v) cin >> to;
    for (int i = 0; i < q; i++) {
        cin >> queries[i].first.first >> queries[i].first.second;
        queries[i].first.first--;
        queries[i].first.second--;
        queries[i].second = i;
    }
    sort(all(queries), [&](pair <pii, int> a, pair <pii, int> b) {
        if (a.first.first/400 == b.first.first/400) {
            return a.first.second < b.first.second;
        }
        return a.first.first/400 < b.first.first/400;
    }); 
    
    int l = 0, r = -1;
    MO mo;
    for (auto to : queries) {
        auto ql = to.first.first, qr = to.first.second, ind = to.second;
        while (r < qr) {
            r++;
            mo.add(v[r]);
        }
        while (l > ql) {
            l--;
            mo.add(v[l]);
        }
        while (r > qr) {
            mo.remove(v[r]);
            r--;
        }
        while (l < ql) {
            mo.remove(v[l]);
            l++;
        }
        ans[ind] = mo.get();
    }
    for (auto to : ans) cout << to << endl;
}

int main() {
    //~ do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    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