Submission #696660

#	Time	Username	Problem	Language	Result	Execution time	Memory
696660		TranGiaHuy1508	Izbori (COCI22_izbori)	C++17	110 / 110	912 ms	8016 KiB

Main

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

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

const int maxn = 6e5 + 5;
int THRESHOLD;
int n;
int a[maxn], heavy[maxn];
int _dp[maxn * 2];
map<int, int> cmp;

void main_program(){
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
		cmp[a[i]] = 1;
	}
	int CL = 0; for (auto &[key, value]: cmp) value = CL++;
	for (int i = 0; i < n; i++) a[i] = cmp[a[i]];

	THRESHOLD = 316;

	for (int i = 0; i < n; i++) heavy[a[i]]++;
	for (int i = 0; i < n; i++) heavy[i] = (heavy[i] > THRESHOLD);

	int* dp = _dp + maxn;
	long long res = 0;

	// Light
	for (int i = 0; i < n; i++){
		int mx = 0;
		for (int j = 0; j < THRESHOLD * 2 + 2; j++){
			if (i + j >= n) break;
			if (!heavy[a[i+j]]){
				dp[a[i+j]]++;
				mx = max(mx, dp[a[i+j]]);
			}
			if ((mx << 1) > (j+1)) res++;
		}
		for (int j = 0; j < THRESHOLD * 2 + 2; j++){
			if (i + j >= n) break;
			if (!heavy[a[i+j]]){
				dp[a[i+j]]--;
			}
		}
	}

	// Heavy
	for (int i = 0; i < n; i++){
		if (!heavy[i]) continue;
		long long less = 0, crr = 0;
		dp[crr]++;

		for (int j = 0; j < n; j++){
			int val = (a[j] == i) ? 1 : -1;
			if (val == 1){
				less += dp[crr];
				crr++;
			}
			else{
				crr--;
				less -= dp[crr];
			}
			dp[crr]++;

			res += less;
		}

		crr = 0; dp[crr]--;
		for (int j = 0; j < n; j++){
			int val = (a[j] == i) ? 1 : -1;
			crr += val;
			dp[crr]--;
		}
	}

	cout << res << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 70 / 70