oj.uz

Submission #1018644

# Submission time Handle Problem Language Result Execution time Memory
1018644 2024-07-10T07:47:18 Z vjudge1 Izbori (COCI22_izbori) C++17
25 / 110
 19 ms 1372 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

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

constexpr uint MOD = 1e9+7;
constexpr uint mod = 998244353;
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();
	const int64_t B = uniform_int_distribution<int64_t>(0, MOD - 1)(rng);
	const int64_t b = uniform_int_distribution<int64_t>(0, mod - 1)(rng);
	template <typename T1, typename T2> inline size_t operator()(pair<T1, T2> const& x) const;
	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);
	}
	inline size_t operator()(string const& x) const {
		int64_t curb = 1, curB = 1, curh = 0, curH = 0;
		for(int i=0; i<x.size(); i++) {
			curh += (curb * this->operator()(x[i])) % mod;
			curH += (curB * this->operator()(x[i])) % MOD;
			curh %= mod;
			curH %= MOD;
			curb = (curb * b) % mod;
			curB = (curB * B) % MOD;
		}
		size_t hash = int64_t(uint(curh)) + (int64_t(uint(curH))<<32);
		return this->operator()(hash);
	}
};
template <typename T1, typename T2> inline size_t chash::operator()(pair<T1, T2> const& x) const {
	return this->operator()((this->operator()(x.F) % MOD + ((this->operator()(x.S) % MOD) * B) % MOD) % MOD);
}

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

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for(auto &x:a) cin >> x;
	if(*max_element(a.begin(), a.end()) <= 2 && *min_element(a.begin(), a.end()) >= 1) {
		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;
		int ans = n;
		for(int i = 0; i < n; i ++) {
			ans += i - 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';
}

Compilation message

Main.cpp: In member function 'size_t chash::operator()(const string&) const':
Main.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for(int i=0; i<x.size(); i++) {
      |                ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 19 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 12 ms 348 KB Output is correct
10 Correct 12 ms 444 KB Output is correct
11 Correct 12 ms 348 KB Output is correct
12 Correct 12 ms 444 KB Output is correct
13 Correct 14 ms 448 KB Output is correct
14 Correct 12 ms 348 KB Output is correct
15 Correct 12 ms 440 KB Output is correct
16 Correct 12 ms 444 KB Output is correct
17 Correct 9 ms 348 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 19 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 12 ms 348 KB Output is correct
10 Correct 12 ms 444 KB Output is correct
11 Correct 12 ms 348 KB Output is correct
12 Correct 12 ms 444 KB Output is correct
13 Correct 14 ms 448 KB Output is correct
14 Correct 12 ms 348 KB Output is correct
15 Correct 12 ms 440 KB Output is correct
16 Correct 12 ms 444 KB Output is correct
17 Correct 9 ms 348 KB Output is correct
18 Incorrect 13 ms 1372 KB Output isn't correct
19 Halted 0 ms 0 KB -