oj.uz

Submission #907487

# Submission time Handle Problem Language Result Execution time Memory
907487 2024-01-15T17:36:53 Z TranGiaHuy1508 Izbori (COCI22_izbori) C++17
0 / 110
 47 ms 6672 KB 
#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 + 5);
	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 + 5, 0), cnt(n * 2 + 5, 0);
	int res = 0;
	int pfx = n + 2; 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];
		compress[v[i]] = 1;
	}

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

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

	int res = 0;
	for (auto [key, value]: mpcnt){
		if (value > threshold){
			vector<int> vec(n);
			for (int i = 0; i < n; i++) vec[i] = (v[i] == key) ? 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.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 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
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 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 6672 KB Execution killed with signal 11
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 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -