Submission #725333

#	Time	Username	Problem	Language	Result	Execution time	Memory
725333		Rafi22	Diversity (CEOI21_diversity)	C++14	100 / 100	3096 ms	10088 KiB

diversity

#include <bits/stdc++.h>
 
using namespace std;
 
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
 
const int N=300007;
 
int a[N];
int ile[N];
int cnt[N];
 
struct qry
{
    int l,r,i;
};
 
const int S=sqrt(300000);
 
bool cmp(qry l,qry r)
{
    if(l.l/S==r.l/S) return l.r<r.r;
    return l.l/S<r.l/S;
}
 
 
ll ans[N];
bool was[N];
 
ll pref[N];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) pref[i]=pref[i-1]+(ll)i*(ll)(i+1)/2;
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<qry>Q;
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        Q.pb({l,r,i});
    }
    sort(all(Q),cmp);
    vector<int>is;
    int l=1,r=0;
    for(auto x:Q)
    {
        while(r<x.r)
        {
            r++;
            cnt[ile[a[r]]]--;
            ile[a[r]]++;
            cnt[ile[a[r]]]++;
            is.pb(ile[a[r]]);
        }
        while(r>x.r)
        {
            cnt[ile[a[r]]]--;
            ile[a[r]]--;
            cnt[ile[a[r]]]++;
            is.pb(ile[a[r]]);
            r--;
        }
        while(l>x.l)
        {
            l--;
            cnt[ile[a[l]]]--;
            ile[a[l]]++;
            cnt[ile[a[l]]]++;
            is.pb(ile[a[l]]);
        }
        while(l<x.l)
        {
            cnt[ile[a[l]]]--;
            ile[a[l]]--;
            cnt[ile[a[l]]]++;
            is.pb(ile[a[l]]);
            l++;
        }
        vector<int>nis;
        for(auto i:is)
        {
            if(i==0||cnt[i]==0) continue;
            if(!was[i]) nis.pb(i);
            was[i]=1;
        }
        is=nis;
        sort(all(is));
        vector<pair<ll,ll>>V1,V2,V;
        int s=0;
        for(auto i:is)
        {
         //   cout<<i<<" "<<cnt[i]<<endl;
            was[i]=0;
            if(s%2==0)
            {
                V1.pb({cnt[i]/2+cnt[i]%2,i});
                if(cnt[i]>1) V2.pb({cnt[i]/2,i});
            }
            else
            {
                if(cnt[i]>1) V1.pb({cnt[i]/2,i});
                V2.pb({cnt[i]/2+cnt[i]%2,i});
            }
            s+=cnt[i];
        }
        for(auto i:V1) V.pb(i);
        reverse(all(V2));
        for(auto i:V2) V.pb(i);
        ll res=0,sum=0,S=0;
      //  cout<<x.i<<endl;
        for(auto x:V)
        {
         //   cout<<x.st<<" "<<x.nd<<" "<<res<<" "<<sum<<" "<<S<<endl;
            res+=x.st*x.nd*(x.nd+1)/2;
         //   cout<<res<<endl;
            res+=S*x.st*x.nd;
          //  cout<<res<<endl;
            res+=sum*(x.st)*(x.st+1)/2*x.nd;
         //   cout<<res<<endl;
            res+=(pref[x.st]-x.st)*x.nd*x.nd;
          //  cout<<res<<endl;
            S+=x.st*sum;
            S+=x.nd*x.st*(x.st+1)/2;
            sum+=x.st*x.nd;
        }
        ans[x.i]=res;
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<endl;
 
 
 
 
    return 0;
}

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