Submission #1094142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094142		icebear	Izbori (COCI22_izbori)	C++14	110 / 110	592 ms	7344 KiB

Main

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

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i, n) for(int i=0; i<(n); ++i)
#define red(i, n) for(int i=(n)-1; i>=0; --i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebearat"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll LLinf = 1e18 + 27092008;
const int N = 2e5 + 5;
const int THRESHOLD = 450;
int n, a[N];
int cnt[N], curCnt[N];

void Compress() {
	vector<int> com;
	FOR(i, 1, n) com.pb(a[i]);
	sort(all(com));
	com.resize(unique(all(com)) - com.begin());

	FOR(i, 1, n) 	
		a[i] = lower_bound(all(com), a[i]) - com.begin() + 1;
}

ll ans = 0;

void lightQuery() {
	FOR(i, 1, n) {
		int mx = 0;
		FOR(j, i, min(i + 2 * THRESHOLD - 1, n)) {
			if (cnt[a[j]] <= THRESHOLD) {
				curCnt[a[j]]++;
				mx = max(mx, curCnt[a[j]]);
			}
			if (2 * mx > (j - i + 1)) ans++;
		}

		FOR(j, i, min(i + 2 * THRESHOLD - 1, n))
			if (cnt[a[j]] <= THRESHOLD)
				curCnt[a[j]]--;
	
	}
}

int arr[N], num[N << 1];
ll dp[N];

void heavyQuery() {
	vector<int> heavy;
	FOR(i, 1, n) 
		if (cnt[a[i]] > THRESHOLD) {	
			heavy.pb(a[i]);
			cnt[a[i]] = 0;
		}

	for(int x : heavy) {
		FOR(i, 1, n)
			arr[i] = (a[i] == x ? +1 : -1);
		
		memset(num, 0, sizeof num);
		memset(dp, 0, sizeof dp);

		int pref = n;
		num[pref]++;
		FOR(i, 1, n) {
			pref += arr[i];
			if (arr[i] > 0) // pref[i] > pref[i - 1]
				dp[i] = dp[i - 1] + num[pref - 1];
			else
				dp[i] = dp[i - 1] - num[pref];
			ans += dp[i];
			num[pref]++;
		}
	}
}

void solve() {
	cin >> n;
	FOR(i, 1, n) cin >> a[i];
	Compress();

	FOR(i, 1, n) cnt[a[i]]++;
	lightQuery();
	heavyQuery();

	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	if (fopen(task".inp", "r")){
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
	int tc = 1;
//     cin >> tc;
	while(tc--) solve();
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:106:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:107:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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