oj.uz

Submission #1018626

# Submission time Handle Problem Language Result Execution time Memory
1018626 2024-07-10T07:39:43 Z vjudge1 Izbori (COCI22_izbori) C++17
25 / 110
 3000 ms 1112 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;
	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 348 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 348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 348 KB Output is correct
7 Correct 20 ms 344 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 348 KB Output is correct
11 Correct 13 ms 344 KB Output is correct
12 Correct 14 ms 344 KB Output is correct
13 Correct 12 ms 348 KB Output is correct
14 Correct 12 ms 348 KB Output is correct
15 Correct 12 ms 348 KB Output is correct
16 Correct 13 ms 348 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 Execution timed out 3034 ms 1112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 348 KB Output is correct
7 Correct 20 ms 344 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 348 KB Output is correct
11 Correct 13 ms 344 KB Output is correct
12 Correct 14 ms 344 KB Output is correct
13 Correct 12 ms 348 KB Output is correct
14 Correct 12 ms 348 KB Output is correct
15 Correct 12 ms 348 KB Output is correct
16 Correct 13 ms 348 KB Output is correct
17 Correct 9 ms 348 KB Output is correct
18 Execution timed out 3034 ms 1112 KB Time limit exceeded
19 Halted 0 ms 0 KB -