Submission #1189464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189464		UmairAhmadMirza	Newspapers (CEOI21_newspapers)	C++20	0 / 100	0 ms	320 KiB

newspapers

#include <bits/stdc++.h>
using namespace std;

#define int long long
int const N=3e5+5;
int const mod=1e9+7;

int cnt[N];

void solve(){
	int n,q;
	cin>>n>>q;
	for (int i = 0; i < n; ++i)
	{
		int a;
		cin>>a;
		cnt[a]++;
	}
	vector<int> v;
	for (int i = 0; i < N; ++i)
		if(cnt[i]>0)
			v.push_back(cnt[i]);
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	int lft=0,rgt=0;
	vector<int> lf,rg;
	for (int c:v)
	{
		if(lft<rgt){
			lf.push_back(c);
			lft+=c;
		}
		else{
			rg.push_back(c);
			rgt+=c;
		}
	}
	reverse(rg.begin(), rg.end());
	for(int i:rg)
		lf.push_back(i);
	vector<int> fn;
	for(int i=1;i<=lf.size();i++){
		for(int j=0;j<lf[i-1];j++)
			fn.push_back(i);
	}
	int ans=0;
	int tot=0;
	for(int i=0;i<fn.size();i++)
		tot+=fn[i];
	ans=tot;
	for(int i=1;i<fn.size();i++){
		tot--;
		if(fn[i]!=fn[i-1])
			tot-=(fn.size())-i;
		ans+=tot;
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		cout<<ans<<endl;
	}
}

signed main(){
	int t=1;
	// cin>>t;
	while(t--)
		solve();
	return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 8
• Subtask 3: 0 / 80