제출 #1164215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164215		MMJ	Izbori (COCI22_izbori)	C++20	40 / 110	3091 ms	3788 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 = 0;

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

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]]++;
	}
	for(int i = 0; i < n; 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;
	}
	cout << ans;
}

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