Submission #650647

#	Time	Username	Problem	Language	Result	Execution time	Memory
650647		1bin	Diversity (CEOI21_diversity)	C++14	4 / 100	15 ms	1492 KiB

diversity

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3e5 + 5;
const int b = 550;
ll n, Q, a[NMAX], ans[NMAX], l, r, c[NMAX], cnt[NMAX], ls, rs, x, y, res;
map<int, int> mp;
struct query{
    int i, l, r;
    bool operator <(const query& x){
        if(l / b == x.l / b) return (l / b & 1) ? r > x.r : r < x.r;
        else return l / b < x.l / b;
    }
} q[NMAX];

void f(int x, int v){
    if(--mp[c[x]] == 0) mp.erase(c[x]);
    cnt[c[x]]--;
    c[x] += v;
    mp[c[x]] = ++cnt[c[x]];
    //for(int i = 1; i <= 3; i++) cout << cnt[i] << ' ';
    //cout << '\n';
    return;
}

ll cal(ll l, ll x, ll c){ return x * (x + 1) * (2 * x + 1) / 6 * c * c + c * (l - c) * x * (x + 1) + (l - c) * (l - c) * x;}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> Q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i < Q; i++) cin >> q[i].l >> q[i].r, q[i].i = i;
    sort(q, q + Q);
    l = 1, r = 0;
    for(int i = 0; i < Q; i++){
        while(l > q[i].l) f(a[--l], 1);
        while(r < q[i].r) f(a[++r], 1);
        while(l < q[i].l) f(a[l++], -1);
        while(r > q[i].r) f(a[r--], -1);
        ls = rs = res = 0;
        //cout << "start qury \n";
        for(auto& [c, t] : mp){
            if(!c) continue;
            x = (t + 1) / 2; y = t - x;
            int n = r - l + 1;
            //cout << c << ' ' << t << '\n';
            res += (n * n + c) * t;
            res -= cal(ls, x, c) + cal(n - ls - c - (x - 1) * c, x, c);
            res -= cal(rs, y, c) + cal(n - rs - c - (y - 1) * c, y, c);
            ls += x * c; rs += y * c;
            if(x > y) swap(ls, rs);
        }
        ans[q[i].i] = res / 2;
    }
    
    for(int i = 0; i < Q; i++) cout << ans[i] << '\n';
    return 0;
}

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:46:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |         for(auto& [c, t] : mp){
      |                   ^

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