제출 #1164315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164315		mmd_matin	Izbori (COCI22_izbori)	C++20	10 / 110	3091 ms	7176 KiB

Main

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5  + 5, sq = 455;
int n, a[N], ans, sm[N * 4];
map <int, int> cnt;
vector <int> mmd, matin;

void read() {
	cin >> n;
	for (int t = 0; t < n; t++) {
		cin >> a[t];
		cnt[a[t]]++;
	}
	for (auto [x, y] : cnt) 
		if (y > sq)
			mmd.push_back(x);
		else
			matin.push_back(x);
}

void update(int id, int ls, int le, int l, int r, int x) {
	if (ls >= r || le <= l)
		return;
	if (ls >= l && le <= r) {
		sm[id] += x;
		return;
	}
	int mid = (ls + le) >> 1;
	update(id << 1, ls, mid, l, r, x);
	update(id << 1 | 1, mid, le, l, r, x);
	sm[id] = sm[id << 1] + sm[id << 1 | 1];
}

int get(int id, int ls, int le, int l, int r) {
	if (ls >= r || le <= l)
		return 0;
	if (ls >= l && le <= r)
		return sm[id];
	int mid = (ls + le) >> 1;
	return get(id << 1, ls, mid, l, r) + get(id << 1 | 1, mid, le, l, r);
}

void solve_big() {
	for (int t = 0; t < mmd.size(); t++) {
		int p[n + 5] = {};
		for (int i = 0; i < n; i++) {
			if (a[i] == mmd[t])
				p[i + 1] = p[i] + 1; 
			else
				p[i + 1] = p[i] - 1;
			p[i] += n + 1;
		}
		p[n] += n + 1;
//		cout << "here : " << mmd[t] << '\n';
//		for (int i = 0; i <=  n; i++)
//			cout << p[i] << ' ';
			
//		cout << '\n';
 		for (int i = 0; i <= n; i++) {
			update(1, 0, n + n + 1, p[i], p[i] + 1, 1);
			ans += get(1, 0, n + n + 1, 0, p[i]);
		}
		for (int i = 0; i <= n;  i++)
			update(1, 0, n + n + 1, p[i], p[i] + 1, -1);
//		cout << "ans : " << ans << '\n';
	}
}

void solve_small() {
	for (int t = 1; t <= min(n, 2 * sq); t++) {
		map <int, int> tmp, count;
		int mx = 1;
		for (int i = 0; i < matin.size(); i++) {
 			count[matin[i]] = 0;
 			tmp[0]++;
		}
		for (int i = 0; i < t; i++) {
			if (cnt[a[i]] <= sq) {
				tmp[count[a[i]]]--;
				count[a[i]]++;
				mx = max(mx, count[a[i]]);
				tmp[count[a[i]]]++;
			}
		}
//		cout << t << ' ' << ans << '\n';
		int pnt = t;
		if (mx > t - mx)
			ans++;
		while (pnt < n) {
			if (cnt[pnt] <= sq) {
				tmp[count[a[pnt]]]--;
				count[a[pnt]]++;
				mx = max(mx, count[a[pnt]]);
				tmp[count[a[pnt]]]++;
			}
			if (cnt[pnt - t] <= sq) {
				tmp[count[a[pnt - t]]]--;
				if (tmp[count[a[pnt - t]]] == 0 && count[a[pnt - t]] == mx)
					mx--;
				count[a[pnt - t]]--;
				tmp[count[a[pnt - t]]]++;
			}
			if (mx > t - mx)
				ans++;
			pnt++;
		}
	}
}

int main() {
	read();
	solve_small();
//	cout << ans << '\n';
	solve_big();
	cout << ans << '\n';
}

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