Submission #519420

#	Time	Username	Problem	Language	Result	Execution time	Memory
519420		AmShZ	Diversity (CEOI21_diversity)	C++11	64 / 100	7041 ms	7880 KiB

diversity

//khodaya khodet komak kon
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 3e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 998244353;
const int base = 257;

int n, q, cnt[xn], a[xn], sum[2];
ll ans;
vector <int> vec[2], V;

ll CR(int n){
	return 1ll * n * (n + 1) / 2;
}

int main(){
	fast_io;

	cin >> n >> q;
	for (int i = 1; i <= n; ++ i)
		cin >> a[i];
	while (q --){
		int l, r;
		cin >> l >> r;
		memset(cnt, 0, sizeof cnt);
		for (int i = l; i <= r; ++ i)
			++ cnt[a[i]];
		V.clear(), vec[0].clear(), vec[1].clear();
		ans = sum[0] = sum[1] = 0;
		for (int i = 0; i < xn; ++ i)
			if (cnt[i])
				V.push_back(cnt[i]);
		sort(all(V));
		for (int x : V){
			if (sum[0] < sum[1])
				vec[0].push_back(x), sum[0] += x;
			else
				vec[1].push_back(x), sum[1] += x;
		}
		reverse(all(vec[1]));
		for (int x : vec[1])
			vec[0].push_back(x);
		int res = 0;
		for (int x : vec[0]){
			ans += CR(r - l + 1) - CR(r - l + 1 - res - x) - CR(res);
			res += x;
		}
		cout << ans << endl;
	}

	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