Submission #1164235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164235		MMJ	Izbori (COCI22_izbori)	C++20	110 / 110	1557 ms	19620 KiB

Main

#include<bits/stdc++.h> 
using namespace std;
 
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("tune=native,avx2")
//#pragma GCC optimize ("Ofast,unroll-loops,trapv")
//#pragma GCC target ("tune=native")
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
typedef pair<ll, pii> mmj;
 
#define f first
#define s second
#define mkpr make_pair
#define pque priority_queue
#define pb push_back
#define pf push_front
#define vec vector
#define Yes cout << "Yes\n";
#define YES cout << "YES\n";
#define No cout << "No\n";
#define NO cout << "NO\n";
#define em(x) (bool)(x).empty()
#define all(x) (x).begin(), (x).end()
#define tc int tc;cin >> tc; while(tc--) 
#define cps CLOCKS_PER_SEC
#define mmj pair<ll, pii>
//setprecision
//int, vector<int>, greater<int>
 
const int N = 2e5 + 5, P = 1e9 + 7, T = 500;

int n, m, h, a[N], b[N], tr[N + N], rep[N];
bool mk[N];
map<int, int> cnt, mp;
ll ans;
set<int> st;

void add(int i) {
	for(; i < N + N; i += i & -i)
		tr[i]++;
}

int get(int i) {
	int res = 0;
	for(; i; i -= i & -i)
		res += tr[i];
	return res;
}

void ch(int x) {
	int pr = n + 2;
	memset(tr, 0, sizeof tr);
	add(pr);
	for(int i = 0; i < n; i++) {
		if(a[i] == x)
			pr++;
		else
			pr--;
		ans += get(pr - 1);
		add(pr);
	}
}

int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		cnt[a[i]]++;
		st.insert(a[i]);
	}
	int t = 0;
	for(auto v: st) 
		mp[v] = t++;
	for(int i = 0; i < n; i++) {
		b[i] = mp[a[i]];
		//cout << b[i] << ' ';
		int x = cnt[a[i]];
		if(cnt[a[i]] > T){
			ch(a[i]);
			cnt[a[i]] = -1;
			mk[i] = 1;
		}
		else if(x == -1)
			mk[i] = 1;
	}
	int mx;
	//cout << '\n';
	for(int i = 0; i < n; i++) {
		m = min(n, i + T + T + 2); 
		mx = b[i];
		for(int j = i; j < m; j++) {
			if(!mk[j]) {
				rep[b[j]]++;
				if(rep[mx] < rep[b[j]])
					mx = b[j];
			}
			//cout << mx;
			if(rep[mx] + rep[mx] > j - i + 1)
				ans++;
		}
		for(int j = i; j < m; j++) 
			if(!mk[j])
				rep[b[j]] = 0;
	}
	cout << ans;
}

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