제출 #1164350

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164350		mmd_matin	Izbori (COCI22_izbori)	C++20	25 / 110	3095 ms	1696 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("tune=native,avx2")
typedef long long ll;
const int N = 2e5  + 5, sq = 550;
int n, a[N], sm[N + N];
ll ans;
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 i, int cnt) {
    while (i <= N + N) {
        sm[i] += cnt;
        i += i & -i;
    }
}
int get(int i) {         // Returns the sum from freq[1] to freq[i]
    int s = 0;
    while (i > 0) {
        s += sm[i];     // Add the sum corresponding to the interval covered by position i
        i -= i & -i;     // Update i to get the next interval
    }
    return s;
} 

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;
		}
//		cout << "here : " << mmd[t] << '\n';
//		for (int i = 0; i <=  n; i++)
//			cout << p[i] << ' ';
//			
//		cout << '\n';
		for (int i = 0; i <= n; i++)
			p[i] += n + 1;
 		for (int i = 0; i <= n; i++) {
			update(p[i], 1);
			ans += get(p[i] - 1);
//			cout << "ans : " << ans << '\n';
		}
		for (int i = 0; i <= n;  i++)
			update(p[i], -1);
	}
//	cout << "done\n";
}

void solve_small() {
	for (int t = 1; t <= min(n, 2 * sq); t++) {
		map <int, int> tmp, count;
		int mx = 0;
		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]]]++;
			}
		}
		ll pnt = t;
		if (mx > t - mx)
			ans++;
		while (pnt < n) {
			if (cnt[a[pnt]] <= sq) {
				tmp[count[a[pnt]]]--;
				count[a[pnt]]++;
				mx = max(mx, count[a[pnt]]);
				tmp[count[a[pnt]]]++;
			}
			if (cnt[a[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() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	read();
	solve_small();
	solve_big();
	cout << ans << '\n';
}

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