Submission #1270466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270466		algoproclub	Izbori (COCI22_izbori)	C++20	110 / 110	1236 ms	6816 KiB

Main

// UUID: 7ebc3345-7eff-46a2-ba7f-8cd2016a1e6c
#include <bits/stdc++.h>
using namespace std;
const int gy=1250,c=4e5+12;
using ll = long long;
ll ans;
int n;
int val[c],g[c],h[c];
void query(int r){
    while (r >= 0){
        ans += val[r];
        r = g[r];
	}
}
void upd(int idx, int delta) {
        for (; idx < 2*n+1; idx = h[idx])
            val[idx] += delta;
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=0; i<=2*n+5; i++)
	{
		g[i]=(i&(i+1))-1;
		h[i]=(i|(i+1));
	}
	vector<int> pontok{0},v(n+1);
	for(int i=1; i<=n; i++)
	{
		cin>>v[i];
		pontok.push_back(v[i]);
	}
	sort(pontok.begin(),pontok.end());
	pontok.erase(unique(pontok.begin(),pontok.end()),pontok.end());
	for(int i=1; i<=n; i++)
	{
		v[i]=lower_bound(pontok.begin(),pontok.end(),v[i])-pontok.begin();
	}
	int mer=pontok.size();
	vector<int> cnt(mer);
	for(int i=1; i<=n; i++)
	{
		cnt[v[i]]++;
	}
	vector<int> db(mer);
	for(int kezd=1; kezd<=n; kezd++)
	{
		int tmp=0;
		for(int i=kezd; i<=min(n,kezd+2*gy); i++)
		{
			if(++db[v[i]]>db[tmp]) tmp=v[i];
			int f=i-kezd+1;
			if(db[tmp]>f/2 && cnt[tmp]<gy) ans++;
		}
		for(int i=kezd; i<=min(n,kezd+2*gy); i++)
			db[v[i]]=0;
	}
		for(int e=1; e<mer; e++)
		{
			if(cnt[e]>=gy)
			{
				for(int i=0; i<=2*n; i++)
					val[i]=0;
				int pref=0;
				upd(n,1);
				for(int i=1; i<=n; i++)
				{
					if(v[i]==e) pref++;
					else pref--;
					query(pref+n-1);
					upd(pref+n,1);
				}
			}
		}
	cout<<ans<<"\n";
}

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