Submission #772301

#	Time	Username	Problem	Language	Result	Execution time	Memory
772301		tolbi	Diversity (CEOI21_diversity)	C++17	64 / 100	4700 ms	22244 KiB

diversity

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz!..
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& is, pair<X,Y> &pr){return is>>pr.first>>pr.second;}
template<typename X, size_t Y> istream& operator>>(istream& is, array<X,Y> arr){for (auto &it : arr) is>>it; return is;}
template<typename T> istream& operator>>(istream& is, vector<T> arr){for (auto &it : arr) is>>it; return is;}
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define endl '\n'
#define int long long
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define vint(x) vector<int> x
#define cinarr(x) for(auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((int)(bi)))
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
int32_t main(){
	ios;
	int T = 1;
	if (!T) cin>>T;
	int tno = 0;
	while (T-(tno++)){
		deci(n);deci(q);
		vint(arr(n));
		cinarr(arr);
		while (q--){
			deci(l);deci(r);
			l--,r--;
			map<int,int> mp;
			for (int i = l; i <= r; i++){
				mp[arr[i]]++;
			}
			arr.clear();
			for (auto it : mp){
				arr.push_back(it.second);
			}
			sortarr(arr);
			vector<int> barr(arr.size(),0);
			int rp = barr.size()-1;
			int lp = 0;
			int lek = 0;
			int rek = 0;
			for (int i = 0; i < arr.size(); i++){
				if (lek<rek){
					barr[lp]=arr[i];
					lp++;
					lek+=arr[i];
				}
				else{
					barr[rp]=arr[i];
					rp--;
					rek+=arr[i];
				}
			}
			int ans = (n*(n+1)/2)*(int)barr.size();
			int somma = 0;
			for (int i = 0; i < barr.size(); i++){
				ans-=somma*(somma+1)/2;
				somma+=barr[i];
			}
			somma=0;
			for (int i = 0; i < barr.size(); i++){
				ans-=somma*(somma+1)/2;
				somma+=barr[barr.size()-i-1];
			}
			cout<<ans<<endl;
		}
	}
}

Compilation message (stderr)

diversity.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
diversity.cpp: In function 'int32_t main()':
diversity.cpp:56:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for (int i = 0; i < arr.size(); i++){
      |                    ~~^~~~~~~~~~~~
diversity.cpp:70:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    for (int i = 0; i < barr.size(); i++){
      |                    ~~^~~~~~~~~~~~~
diversity.cpp:75:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    for (int i = 0; i < barr.size(); i++){
      |                    ~~^~~~~~~~~~~~~

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