Submission #1270449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270449		algoproclub	Izbori (COCI22_izbori)	C++20	40 / 110	3092 ms	8292 KiB

Main

// UUID: f23eab7a-19e4-427a-b034-0f40c5ded1e9
#include <bits/stdc++.h>
using namespace std;
const int gy=1500,c=4e5+12;
using ll = long long;
int val[4*c];
void upd(int cs, int tl, int tr, int pos)
{
	if(tl==tr)
	{
		val[cs]++;
		return;
	}
	int mid=(tl+tr)/2;
	if(pos<=mid) upd(2*cs,tl,mid,pos);
	else upd(2*cs+1,mid+1,tr,pos);
	val[cs]=val[2*cs]+val[2*cs+1];
}
int query(int cs, int tl, int tr, int l, int r)
{
	if(l>r) return 0;
	if(l==tl && r==tr) return val[cs];
	int mid=(tl+tr)/2;
	return query(2*cs,tl,mid,l,min(r,mid))+query(2*cs+1,mid+1,tr,max(mid+1,l),r);
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin>>n;
	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]]++;
	}
	ll ans=0;
	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 h=i-kezd+1;
			if(db[tmp]>h/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=1; i<=8*n; i++)
					val[i]=0;
				int pref=0;
				upd(1,0,2*n+2,n);
				for(int i=1; i<=n; i++)
				{
					if(v[i]==e) pref++;
					else pref--;
					ans+=ll(query(1,0,2*n+2,0,pref+n-1));
					upd(1,0,2*n+2,pref+n);
				}
			}
		}
	cout<<ans<<"\n";
}

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