Submission #907484

#	Time	Username	Problem	Language	Result	Execution time	Memory
907484		TranGiaHuy1508	Izbori (COCI22_izbori)	C++17	0 / 110	38 ms	6676 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();
}

#define int long long

int n, threshold;
vector<int> v;

map<int, int> compress, mpcnt;

int solve_light(vector<int> &V){
	vector<int> CNT(n + 1);
	int res = 0;
	for (int l = 0; l < n; l++){
		int mx = 0;
		for (int r = l; r <= min(n - 1, l + threshold * 2); r++){
			if (V[r] >= 0) mx = max(mx, ++CNT[V[r]]);
			if (mx * 2 > (r - l + 1)){
				res++;
			}
		}
		for (int r = l; r <= min(n - 1, l + threshold * 2); r++){
			CNT[V[r]]--;
		}
	}
	return res;
}

int solve_heavy(vector<int> &V){
	vector<int> dp(n * 2 + 3, 0), cnt(n * 2 + 3, 0);
	int res = 0;
	int pfx = n + 1; cnt[pfx]++;

	for (int i = 0; i < n; i++){
		pfx += V[i];
		cnt[pfx]++;
		dp[pfx] = dp[pfx - 1] + cnt[pfx - 1];
		res += dp[pfx];
	}

	return res;
}

void main_program(){
	cin >> n;
	v.resize(n);

	threshold = sqrt(n);

	for (int i = 0; i < n; i++){
		cin >> v[i];
		mpcnt[v[i]]++;
		compress[v[i]] = 1;
	}

	int crr = 1;
	for (auto &[key, value]: compress) value = crr++;
	for (auto &key: v) key = compress[key];

	int res = 0;
	for (auto [key, value]: mpcnt){
		if (value > threshold){
			vector<int> vec(n);
			int newkey = compress[key];
			for (int i = 0; i < n; i++) vec[i] = (v[i] == newkey) ? 1 : -1;
			res += solve_heavy(vec);
		}
	}

	int bruhbruh = -1;
	for (int i = 0; i < n; i++){
		if (mpcnt[v[i]] > threshold){
			v[i] = --bruhbruh;
		}
	}

	res += solve_light(v);

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

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