Submission #474467

#	Time	Username	Problem	Language	Result	Execution time	Memory
474467		lory1608	Diversity (CEOI21_diversity)	C++17	64 / 100	23 ms	4560 KiB

diversity

//#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
#define ll long long
#define pb push_back
#define sz(x) (int)(x.size())
#define gc getchar()
#define mk make_pair
//#define gc (_p1==_p2&&(_p2=(_p1=_buf)+fread(_buf,1,100000,stdin),_p1==_p2)?EOF:*_p1++)
using namespace std;
char _buf[100000],*_p1=_buf,*_p2=_buf;
inline int gi()
{
	int x=0,f=1;
	char ch=gc;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=gc;
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+(ch^48);
		ch=gc;
	}
	return (f==1)?x:-x;
}
const int maxn=3e5+5,M=3e5;
int n,Q,a[maxn],cnt[maxn];
int lp,rp;
inline void input()
{
	n=gi();Q=gi();
	FOR(i,1,n)a[i]=gi(),cnt[a[i]]++;
	sort(cnt+1,cnt+M+1);
}
inline void solve()
{
	ll ans=0;
	FOR(i,1,M)
	{
		if(cnt[i]==0)continue;
		if(lp>rp)swap(lp,rp);
		ans+=1ll*n*(n+1)/2;
		ans-=1ll*lp*(lp+1)/2;
		ans-=1ll*(n-lp-cnt[i])*(n-lp-cnt[i]+1)/2;
		lp+=cnt[i];
	}
	printf("%lld\n",ans);
}
int main()
{
	//freopen("diversity.in","r",stdin);
	//freopen("diversity.out","w",stdout);
	input();
	solve();
	return 0;
}

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