Submission #1169898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169898		ByeWorld	Diversity (CEOI21_diversity)	C++20	64 / 100	7092 ms	2520 KiB

diversity

#include <bits/stdc++.h>
// #define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<char,char> pcc;
typedef pair<pii,int> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+10;
const int SQRT = 600;
const int MAXA = 1e5;
const int LOG = 20;
const int INF = 1e18+10;
const ld EPS = 1e-6;
const int MOD = 998244353;
int sum(int a, int b){ return (a+b)%MOD; }
void chsum(int &a, int b){ a = (a+b)%MOD; }
void chsub(int &a, int b){ a = (a+MOD-b)%MOD; }
int mul(int a, int b){ return (a*b)%MOD; }
void chmul(int &a, int b){ a = (a*b)%MOD; }
void chmn(int &a, int b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }

int n, q, a[MAXN], cnt[MAXN];
int siz;
vector <ipii> que;
bool cmp(ipii a, ipii b){
    if(a.fi.fi/SQRT != b.fi.fi/SQRT) a.fi.fi/SQRT < b.fi.fi/SQRT;
    return a.fi.se < b.fi.se;
}

int l=1,r=0, dif[MAXN];
set<int> ma;
void move(int le, int ri){
    while(le < l){
        l--; 
        dif[cnt[a[l]]]--; 
        if(dif[cnt[a[l]]] == 0) ma.erase(cnt[a[l]]);

        cnt[a[l]]++; 
        dif[cnt[a[l]]]++;
        if(dif[cnt[a[l]]] == 1) ma.insert(cnt[a[l]]);
    }
    while(r < ri){
        r++; 
        dif[cnt[a[r]]]--; 
        if(dif[cnt[a[r]]] == 0) ma.erase(cnt[a[r]]);

        cnt[a[r]]++; 
        dif[cnt[a[r]]]++;
        if(dif[cnt[a[r]]] == 1) ma.insert(cnt[a[r]]);
    }
    while(l < le){
        if(dif[cnt[a[l]]] == 1) ma.erase(cnt[a[l]]);
        dif[cnt[a[l]]]--; 
        cnt[a[l]]--; 

        if(dif[cnt[a[l]]] == 0) ma.insert(cnt[a[l]]);
        dif[cnt[a[l]]]++; 
        l++; 
    }
    while(ri < r){
        if(dif[cnt[a[r]]] == 1) ma.erase(cnt[a[r]]);
        dif[cnt[a[r]]]--; 
        cnt[a[r]]--; 

        if(dif[cnt[a[r]]] == 0) ma.insert(cnt[a[r]]);
        dif[cnt[a[r]]]++; 
        r--;  
    }
}
ll dua(ll x){ return 1ll*x*(x+1)/2; }
ll tiga(ll x){ return 1ll*x*(x+1)*(2*x+1)/6; }
pii opt[MAXN]; 
ll ans[MAXN];

signed main(){
    ios_base::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 p=1; p<=q; p++){
        int l,r;cin>>l>>r;
        que.pb({{l,r}, p});
    }
    sort(que.begin(), que.end(), cmp);

    for(auto [xx, idx] : que){
        move(xx.fi, xx.se);

        vector <pii> vec; 
        ll run = 0, lenreal = 0;
        for(auto in : ma){
            vec.pb(pii(in, dif[in])); // value, len
            lenreal += 1ll*in*dif[in];
            // cout << in << ' ' << dif[in] << " dif\n";
        }
        // cout << lenreal << " lenreal\n";
        reverse(vec.begin(), vec.end());
        assert(vec.empty() < 2*SQRT);

        int L = MAXA, R = MAXA; bool isle = 1; // terakhir ada di left?
        opt[L] = vec[0];
        for(int i=0; i<vec.size(); i++){
            auto [val, len] = vec[i];
            run += 1ll * len * val*(lenreal-val); 
            run += 1ll * len * val*(val+1)/2;

            if(i==0) continue;
            int a, b;
            if((len & 1) == 0) a = len/2, b = len/2;
            else {
                if(isle) a = len/2, b = len/2+1, isle = 0; // right nambahin
                else a = len/2+1, b = len/2, isle = 1; // left tambahin, ke left
            }
            if(a!=0) opt[--L] = pii(val, a);
            if(b!=0) opt[++R] = pii(val, b);
        }
        // cout << run << " RUNN\n";

        vector <pii> seg; seg.pb({-1,-1}); vector <ll> pr; pr.pb(0);
        for(int i=L; i<=R; i++){
            // cout << i << ' ' << opt[i].fi<<' '<<opt[i].se << " opt\n";
            seg.pb(opt[i]);
            pr.pb(pr.back() + 1ll*opt[i].se*opt[i].fi);
        }
        pr.pb(-INF); 
        vector <ll> su; su.resize(pr.size()); su.back() = 0;
        for(int i=R; i>=L; i--) 
            su[i-L+1] = (su[i-L+2] + 1ll*opt[i].se*opt[i].fi);
        su[0] = -INF; 

    //     for(auto in : pr) cout<<in<<' ';
    //     cout << '\n';
    //     for(auto in : su) cout << in<<' ';
    //     cout << '\n';
    // cout << seg.size()<< " seg\n";

        ll val = 0; 
        for(int i=1; i<seg.size(); i++){
            auto [v, len] = seg[i];
            int p = pr[i-1], q = su[i+1], lenv = len*v-v;
            ll nw = 1ll*len*p*(q+lenv) + 1ll*(q+lenv-p)*v*dua(len-1)
                - 1ll*v*v*tiga(len-1);
                // cout << i << ' ' << nw << " nw\n";
                // cout << len*p*(q+lenv) << ' '<< (q+lenv-p)*v*dua(len-1)
                // << ' '<< - v*v*tiga(len-1) << "nwjuga\n";

            val += nw;
        }   
        // cout << val << ' '<< run << "\n\n";

        ans[idx] = val + run;
    }
    for(int i=1; i<=q; i++) cout << ans[i] << '\n';
}
/*

    int ans = 0;
    for(int i=1; i<=300000; i++){
        int len = cnt[i];
        ans += len * (n-len);
        ans += len*(len+1)/2;
        if(cnt[i] != 0) vec.pb(cnt[i]);
    }
    sort(vec.rbegin(), vec.rend());
    siz = vec.size();
    opt.resize(siz);

    int l=siz/2, r=siz/2-1;
    for(int i=0; i<siz; i++){
        if(i%2==0) opt[++r] = vec[i];
        else opt[--l] = vec[i];
    }
    // for(auto in : opt) cout << in << ' ';
    // cout << '\n';
    for(int i=0; i<siz; i++){
        if(i!=0) pr[i] = pr[i-1]+opt[i];
        else pr[i] = opt[i];
    }
    for(int i=siz-1; i>=0; i--)
        su[i] = su[i+1]+opt[i];

    int nw = 0;
    for(int i=0; i<siz; i++){
        nw += (i==0?0:pr[i-1]) * (i+1==siz?0:su[i+1]);
    }

    cout << run+nw << '\n';
*/

Compilation message (stderr)

diversity.cpp:20:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   20 | const int INF = 1e18+10;
      |                 ~~~~^~~

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