Submission #1018970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018970		aeg	Izbori (COCI22_izbori)	C++17	40 / 110	3075 ms	22572 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

#define int int64_t

random_device rd;
mt19937_64 rng(rd.entropy() != 0 ? rd() : chrono::high_resolution_clock::now().time_since_epoch().count());

constexpr long double PI = 3.14159265358979323846264; // PI 23 decimal digit
struct chash {
	static constexpr int64_t C = int64_t(2e18 * PI) + 23;
	const int64_t RANDOM = rng();
	template <typename T, enable_if_t<is_integral<T>::value, bool> = true>
	inline size_t operator()(T const& x) const {
		return __builtin_bswap64((int64_t(x)^RANDOM)*C);
	}
};

template <typename T1, typename T2> using cmap = __gnu_pbds::gp_hash_table<T1, T2, chash>;

int32_t main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for(auto &x:a) cin >> x;
	if(*max_element(a.begin(), a.end()) <= 2) {
		for(int i = 0; i < n; i ++) if(a[i] == 2) a[i] = -1;
		vector<int> pref(n);
		pref[0] = a[0];
		for(int i = 1; i < n; i ++) pref[i] = a[i] + pref[i - 1];
		cmap<int, int> s;
		s[0] ++;
		int ans = 0;
		for(int i = 0; i < n; i ++) {
			ans += i + 1 - s[pref[i]];
			s[pref[i]] ++;
		}
		cout << ans << '\n';
		return 0;
	}
	int ans = 0;
	for(int i = 0; i < n; i ++) {
		cmap<int, int> m;
		int curmax = 0;
		for(int j = i; j < n; j ++) {
			m[a[j]]++;
			curmax = max(curmax, m[a[j]]);
			if(curmax > (j - i + 1) / 2) ans++;
		}
	}
	cout << ans << '\n';
}

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