Submission #576886

#	Time	Username	Problem	Language	Result	Execution time	Memory
576886		talant117408	Diversity (CEOI21_diversity)	C++17	100 / 100	4867 ms	5912 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;

int64_t calc(int64_t n) {
    return (n*(n+1)) >> 1;
}

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

struct MO {
    vector <int> freq, cfreq, comp;
    vector <bool> used;
    int N;
    
    MO() {
        N = 0;
        freq.resize(MAXN);
        cfreq.resize(MAXN);
        used.resize(MAXN);
    }
    void add(int n) {
        cfreq[freq[n]]--;
        freq[n]++;
        if (++cfreq[freq[n]] == 1 && !used[freq[n]]) {
            comp.pb(freq[n]);
            used[freq[n]] = 1;
        }
        N++;
    }
    void remove(int n) {
        cfreq[freq[n]]--;
        freq[n]--;
        if (++cfreq[freq[n]] == 1 && !used[freq[n]] && freq[n] > 0) {
            comp.pb(freq[n]);
            used[freq[n]] = 1;
        }
        N--;
    }
    int64_t get() {
        int saizu = 0;  
        vector <pii> options;
        vector <int> comp1;
        for (auto x : comp) {
            if (cfreq[x] > 0) {
                options.pb(mp(x, cfreq[x]));
                comp1.pb(x);
            }
            else {
                used[x] = 0;
            }
        }
        comp = comp1;
        sort(rall(options));
        deque <pii> dq;
        for (auto x : options) {
            if (saizu % 2 == 0) {
                dq.push_front(mp(x.first, (x.second+1) >> 1));
                if (x.second > 1)
                    dq.push_back(mp(x.first, x.second >> 1));
            }
            else {
                if (x.second > 1) 
                    dq.push_front(mp(x.first, x.second >> 1));
                dq.push_back(mp(x.first, (x.second+1) >> 1));
            }
            saizu += x.second;
        }
        int64_t pref = 0, suff;
        int64_t ans = 0;
        for (auto p : dq) {
            int x = p.first, k = p.second;
            suff = N - pref - x;
            int64_t a = k*calc(x);
            int64_t b = k*pref + x*calc(k-1);
            int64_t c = k*suff - x*calc(k-1);
            int64_t d = k*pref*suff + x*(suff*calc(k-1) - pref*calc(k-1) - x*calc2(k-1));
            ans += a + b*x + c*x + d;
            pref += k*x;
        }
        return ans;
    }
};

void solve() {
    int n, q;
    //~ cin >> n >> q;
    scanf("%d%d", &n, &q);
    
    int BLOCK = 350;
    vector <int> v(n);
    vector <int64_t> ans(q);
    vector <pair <pii, int>> queries(q);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }
    for (int i = 0; i < q; i++) {
        //~ cin >> queries[i].first.first >> queries[i].first.second;
        scanf("%d%d", &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/BLOCK == b.first.first/BLOCK) {
            return a.first.second < b.first.second;
        }
        return a.first.first/BLOCK < b.first.first/BLOCK;
    }); 
    
    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) printf("%lld\n", to);
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

Compilation message (stderr)

diversity.cpp: In function 'void solve()':
diversity.cpp:153:36: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'long int' [-Wformat=]
  153 |     for (auto to : ans) printf("%lld\n", to);
      |                                 ~~~^     ~~
      |                                    |     |
      |                                    |     long int
      |                                    long long int
      |                                 %ld
diversity.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
diversity.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         scanf("%d", &v[i]);
      |         ~~~~~^~~~~~~~~~~~~
diversity.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         scanf("%d%d", &queries[i].first.first, &queries[i].first.second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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