Submission #478794

#	Time	Username	Problem	Language	Result	Execution time	Memory
478794		kshitij_sodani	Diversity (CEOI21_diversity)	C++14	64 / 100	7041 ms	26968 KiB

diversity

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
//vector<llo> adj[200001];
int it[300001];
//llo dp[300001];//[30001];
//llo dp2[300001];
llo pre[300001];
llo ans2[300001];
const llo cc=400;
bool cmp(pair<pair<llo,llo>,llo> aa,pair<pair<llo,llo>,llo> bb){
	llo x=aa.a.a/cc;
	llo y=bb.a.a/cc;
	if(x<y){
		return true;
	}
	else if(x>y){
		return false;
	}
	return aa.a.b<bb.a.b;
}
int freq[300001];
int cnt[300001];
set<int> xx;
void add(int i){
	cnt[freq[it[i]]]--;
	if(cnt[freq[it[i]]]==0 and freq[it[i]]>0){
		xx.erase(freq[it[i]]);
	}
	freq[it[i]]++;
	cnt[freq[it[i]]]++;
	if(cnt[freq[it[i]]]==1){
		xx.insert(freq[it[i]]);
	}
}
void remove(int i){
	cnt[freq[it[i]]]--;
	if(cnt[freq[it[i]]]==0 and freq[it[i]]>0){
		xx.erase(freq[it[i]]);
	}
	freq[it[i]]--;
	cnt[freq[it[i]]]++;
	if(cnt[freq[it[i]]]==1 and freq[it[i]]>0){
		xx.insert(freq[it[i]]);
	}

}
llo pre2[300001];
llo pre3[300001];

llo cal(llo su,llo j,llo yy){
	//sum of squares of (su+j),(su+2*j),,,,(su+yy*j)
	//ans+=cal(su,j,yy);
	llo ac=0;
	ac+=su*su*yy;
	ac+=((pre3[j]-j)*pre2[yy]);
	ac+=(su*j*pre3[yy]);//((yy*(yy+1))));
	//cout<<su<<":"<<j<<":"<<yy<<":"<<ac<<endl;
	return ac;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	for(llo i=1;i<=300000;i++){
		pre2[i]=(((i*(i+1)*(2*i+1))/6));
	}
	for(llo i=1;i<=300000;i++){
		pre3[i]=(i*(i+1));
	}
	llo n,q;
	cin>>n>>q;
	map<llo,llo> ss;
	for(llo i=0;i<n;i++){
		cin>>it[i];
		ss[it[i]]++;
	}
	vector<llo> tt;
	for(auto j:ss){
		tt.pb(j.b);
	}
	sort(tt.begin(),tt.end());
	for(llo i=1;i<=tt.size();i++){
		pre[i]=pre[i-1]+tt[i-1];
	}
	llo m=tt.size();
	llo ans=m*n*(n+1)-(m-1)*n;

	/*vector<llo> ee;
	for(llo i=0;i<tt.size();i+=2){
		ee.pb(tt[i]);
	}
	for(llo i=tt.size()-1;i>=0;i--){
		if(i%2==1){
			ee.pb(tt[i]);
		}
	}*/
	llo su=0;
	//cout<<ans<<endl;
	/*for(llo i=0;i+1<ee.size();i++){
		su+=ee[i];
		ans-=su*su;
		ans-=(n-su)*(n-su);
	}
*/
/*	for(auto j:ee){
		cout<<j<<",";
	}
	cout<<endl;*/
	//cout<<ans<<endl;
	/*if(m==1){

	}
	else{
		for(llo i=0;i<tt.size();i++){
			for(llo j=0;j<=n;j++){
				dp[j]=-(llo)1e18;
			}
			if(i==0){
				dp[tt[0]]=tt[0]*tt[0]+(n-tt[0])*(n-tt[0]);
			}
			else{
				for(llo j=0;j<=n;j++){
					llo cur=j+pre[tt.size()]-pre[i];
					llo su=0;
					su+=cur*cur;
					su+=(n-cur)*(n-cur);
					if(cur==n or cur==0){
						su=0;
					}
					dp[j]=max(dp[j],dp2[j]+su);
					if(j>=tt[i]){
						llo cur=j;
						llo su=0;
						su+=cur*cur;
						su+=(n-cur)*(n-cur);
						if(cur==n or cur==0){
							su=0;
						}
						dp[j]=max(dp[j],dp2[j-tt[i]]+su);
					}
				}
			}
			for(llo j=0;j<=n;j++){
				dp2[j]=dp[j];
			}
		}
		llo ma=0;
		for(llo i=0;i<=n;i++){
			ma=max(ma,dp[i]);
		}
		ans-=ma;
	}*/
	//ans/=2;


	//divide ans/2
	vector<pair<pair<llo,llo>,llo>> qq;
	for(llo i=0;i<q;i++){
		llo l,r;
		cin>>l>>r;
		l--;
		r--;
		qq.pb({{l,r},i});
		//cout<<ans<<endl;
	}
	sort(qq.begin(),qq.end(),cmp);
	llo l=0;
	llo r=0;
	add(l);
	vector<llo> aa;
	for(auto j:qq){
		llo l2=j.a.a;
		llo r2=j.a.b;
		while(l>l2){
			l--;	
			add(l);
		}
		while(r<r2){
			r++;
			add(r);
		}
		while(l<l2){
			remove(l);
			l++;
		}
		while(r>r2){
			remove(r);
			r--;
		}
	/*	for(auto j:xx){
			cout<<j<<",";
		}
		cout<<endl;*/
		/*if(l2==r2){
			ans2[j.b]=1;
			continue;
		}*/
		//aa.clear();
		llo mm=0;
		for(auto j:xx){
			//aa.pb(j);
			mm+=cnt[j];
		}
		if(mm==1){
			ans2[j.b]=((r2-l2+1)*(r2-l2+2))/2;
			continue;
		}
		llo nn=r2-l2+1;
		llo ans=mm*nn*(nn+1)-(mm-1)*nn;
		//cout<<ans<<"::"<<endl;
		llo cur=0;
		llo su=0;
		for(auto j:xx){
			llo yy;
			if(cur&1){
				yy=cnt[j]/2;
			}
			else{
				yy=(cnt[j]+1)/2;
				
			}
			if(yy>0){
				//sum of squares of (su+j),(su+2*j),,,,(su+yy*j)
				ans-=cal(su,j,yy);
				ans-=cal(nn-(su+j*yy)-j,j,yy);

				/*ans+=su*yy;
				ans+=((j*j)*(((yy*(yy+1)*(2*yy+1))/6)));
				ans+=(su*((yy*(yy+1))/2));*/
			}
			su+=yy*j;
			cur+=cnt[j];
		}
		ans=(ans+(su*su)+((nn-su)*(nn-su)));
		//cout<<su<<"::"<<endl;
		//reverse(aa.begin(),aa.end());
		su=0;
		cur=1;
		//cout<<cnt[1]<<"::"<<endl;
		for(auto j:xx){
			llo yy;
			if(cur&1){
				yy=(cnt[j])/2;
			}
			else{
				yy=(cnt[j]+1)/2;
			}
			if(yy>0){
				//sum of squares of (su+j),(su+2*j),,,,(su+yy*j)
				ans-=cal(su,j,yy);
				ans-=cal(nn-(su+j*yy)-j,j,yy);

				/*ans+=su*yy;
				ans+=((j*j)*(((yy*(yy+1)*(2*yy+1))/6)));
				ans+=(su*((yy*(yy+1))/2));*/
			}
			su+=yy*j;
			cur+=cnt[j];
		}

		ans/=2;
		ans2[j.b]=ans;
		//cout<<ans<<endl;
		//

	}

 
	for(llo i=0;i<q;i++){
		cout<<ans2[i]<<endl;
	}
 
	return 0;
}

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:88:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for(llo i=1;i<=tt.size();i++){
      |              ~^~~~~~~~~~~
diversity.cpp:92:6: warning: unused variable 'ans' [-Wunused-variable]
   92 |  llo ans=m*n*(n+1)-(m-1)*n;
      |      ^~~
diversity.cpp:103:6: warning: unused variable 'su' [-Wunused-variable]
  103 |  llo su=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