Submission #790532

#	Time	Username	Problem	Language	Result	Execution time	Memory
790532		CSQ31	Diversity (CEOI21_diversity)	C++17	4 / 100	24 ms	2636 KiB

diversity

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 2e5+5,blk = 450;
int a[MAXN];
struct que{
	int l,r,id;
	que(){}
	que(int _l,int _r,int _id):l(_l),r(_r),id(_id){}
	bool operator<(const que &q){
		if((l+blk-1)/blk &1)return make_pair((l+blk-1)/blk,r) < make_pair((q.l+blk-1)/blk,q.r);
		return make_pair((l+blk-1)/blk,-r) < make_pair((q.l+blk-1)/blk,-q.r);
	}
};
int cnt[MAXN],freq[MAXN];
set<int>s;
void add(int x,int c){
	if(freq[cnt[x]] == 1)s.erase(cnt[x]);
	freq[cnt[x]]--;
	cnt[x]+=c;
	freq[cnt[x]]++;
	if(freq[cnt[x]] == 1)s.insert(cnt[x]);
}
ll cal(int n){
	vector<int>v;
	int T = 0;
	for(int x:s){
		v.pb(x);
		T+=freq[x];
	}
	int t = sz(v);
	vector<int>in(t);
	//ans = 1/2(T*n*n + n - sum of squares)
	//for(int x:v)cout<<x<<" ";cout<<'\n';
	//for(int x:v)cout<<freq[x]<<" ";cout<<'\n';
	ll res = T*1LL*n*1LL*n + n,cur = 0;
	//cout<<"res "<<res<<'\n';
	
	vector<int>lf,rg;
	int turn = 0;
	for(int i=0;i<t;i++){
		for(int j=0;j<freq[v[i]];j++){
			if(!turn)lf.pb(v[i]);
			else rg.pb(v[i]);
			turn^=1;
		}
	}
	reverse(all(rg));
	for(int x:rg)lf.pb(x);
	
	ll sum = 0;
	for(int x:lf){
		res-=sum*sum;
		sum+=x;
	}
	reverse(all(lf));
	sum = 0;
	for(int x:lf){
		res-=sum*sum;
		sum+=x;
	}
	reverse(all(lf));
	return res/2;
}
int main()
{
	owo
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	vector<que>qq(q);
	for(int i=0;i<q;i++){
		int l,r;
		cin>>l>>r;
		qq[i] = que(l,r,i);
	}
	sort(all(qq));
	vector<ll>ans(q);
	int L = 1,R = 0;
	for(int i=0;i<q;i++){
		int l = qq[i].l;
		int r = qq[i].r;
		while(L>l){
			L--;
			add(a[L],1);
		}
		while(L<l){
			add(a[L],-1);
			L++;
		}
		while(R<r){
			R++;
			add(a[R],1);
		}
		while(R>r){
			add(a[R],-1);
			R--;
		}
		//cout<<"TES"<<'\n';
		ans[qq[i].id] = cal(r-l+1);		
	}
	for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
	
	
}

Compilation message (stderr)

diversity.cpp: In function 'll cal(int)':
diversity.cpp:54:29: warning: unused variable 'cur' [-Wunused-variable]
   54 |  ll res = T*1LL*n*1LL*n + n,cur = 0;
      |                             ^~~

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