제출 #805648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
805648		MohamedAhmed04	Izbori (COCI22_izbori)	C++14	0 / 110	13 ms	7628 KiB

Main

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;
const int B = 448 ;

int arr[MAX] ;
int n ;

vector<int>occ[MAX] ;

void compress()
{
	vector<int>v ;
	for(int i = 1 ; i <= n ; ++i)
		v.push_back(arr[i]) ;
	sort(v.begin() , v.end()) ;
	v.erase(unique(v.begin() , v.end()) , v.end()) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		arr[i] = lower_bound(v.begin() , v.end() , arr[i]) - v.begin() ;
		arr[i]++ ;
	}
}

int freq[MAX] ;

long long solve_big(int x)
{
	for(int i = 0 ; i <= 3*n ; ++i)
		freq[i] = 0 ;
	int idx = n-1 , cur = n ;
	long long ans = 0 , cnt = 0 ;
	freq[n]++ , cnt = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(arr[i] == x)
			idx++ , cnt += freq[idx] , ++cur ;
		else
			cnt -= freq[idx] , --idx , --cur ;
		ans += cnt ;
		freq[cur]++ ; 
		if(cur <= idx)
			cnt++ ;
	}
	return ans ;
}

long long calc(int l , int r)
{
	return (1ll * r * (r+1ll) / 2ll - 1ll * (l-1) * (l) / 2ll) ;
}

long long solve_small(int x)
{
	long long ans = 0 ;
	int sz = occ[x].size() ;
	for(int i = 0 ; i < sz ; ++i)
	{
		for(int j = 0 ; j <= i ; ++j)
		{
			int cnt = i-j+1 - (occ[x][i] - occ[x][j] + 1 - (i-j+1)) - 1 ;
			int a = occ[x][j] , b = n+1 - occ[x][i] ;
			if(j > 0)
				a -= occ[x][j-1] ;
			if(i+1 < sz)
				b = occ[x][i+1] - occ[x][i] ;
			if(x < 0)
				continue ;
			// start at occ[x][j]
			ans += min(cnt+1 , b) , --a ;
			// end at occ[x][i]
			ans += min(cnt , a) , --b ;
			// start < oxx[x][j] and end > oxx[j][i]
			int y = max(0 , min(cnt-a , b)) ;
			ans += 1ll * a * y ;
			b -= y , cnt -= y ;
			ans += calc(cnt - min(cnt , b) , cnt-1) ;
		}
	}
	return ans ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	compress() ;
	for(int i = 1 ; i <= n ; ++i)
		occ[arr[i]].push_back(i) ;
	long long ans = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(occ[i].size() >= B)
			ans += solve_big(i) ;
		else
			ans += solve_small(i) ;
	}
	return cout<<ans<<"\n" , 0 ;
}		

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