Submission #576858

#	Time	Username	Problem	Language	Result	Execution time	Memory
576858		talant117408	Diversity (CEOI21_diversity)	C++17	0 / 100	1 ms	1492 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;
    map <int, int> comp;
    int N;
    
    MO() {
        N = 0;
        freq.resize(MAXN);
    }
    void add(int n) {
        if (freq[n]) comp[freq[n]]--;
        freq[n]++;
        comp[freq[n]]++;
        N++;
    }
    void remove(int n) {
        comp[freq[n]]--;
        freq[n]--;
        if (freq[n]) comp[freq[n]]++;
        N--;
    }
    int64_t get() {
        int saizu = 0;  
        deque <pii> K;
        for (auto rit = comp.rbegin(); rit != comp.rend(); rit++) {
            auto x = *rit;
            if (saizu % 2 == 0) {
                K.push_front(mp(x.first, (x.second+1) >> 1));
                if (x.second > 1)
                    K.push_back(mp(x.first, x.second >> 1));
            }
            else {
                if (x.second > 1) 
                    K.push_front(mp(x.first, x.second >> 1));
                K.push_back(mp(x.first, (x.second+1) >> 1));
            }
            saizu += x.second;
        }
        int64_t l = 0, r;
        int64_t ans = 0;
        for (auto p : K) {
            int x = p.first, k = p.second;
            r = N-l-x;
            int64_t a = k*calc(x);
            int64_t b = k*l + x*calc(k-1);
            int64_t c = k*r - x*calc(k-1);
            int64_t 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;
    
    int BLOCK = sqrt(n);
    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++) {
        scanf("%d%d", &queries[i].first.first, &queries[i].first.second);
        //~ 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/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:132:36: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'long int' [-Wformat=]
  132 |     for (auto to : ans) printf("%lld\n", to);
      |                                 ~~~^     ~~
      |                                    |     |
      |                                    |     long int
      |                                    long long int
      |                                 %ld
diversity.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%d", &v[i]);
      |         ~~~~~^~~~~~~~~~~~~
diversity.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         scanf("%d%d", &queries[i].first.first, &queries[i].first.second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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