Submission #805649

# Submission time Handle Problem Language Result Execution time Memory
805649 2023-08-03T19:28:55 Z MohamedAhmed04 Izbori (COCI22_izbori) C++14
25 / 110
12 ms 7412 KB
#include <bits/stdc++.h>

using namespace std ;

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

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 ;
}		
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 4 ms 5104 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 5048 KB Output is correct
10 Correct 3 ms 5048 KB Output is correct
11 Correct 3 ms 5044 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5048 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 5048 KB Output is correct
17 Correct 3 ms 5064 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 7412 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 4 ms 5104 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 5048 KB Output is correct
10 Correct 3 ms 5048 KB Output is correct
11 Correct 3 ms 5044 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5048 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 5048 KB Output is correct
17 Correct 3 ms 5064 KB Output is correct
18 Incorrect 12 ms 7412 KB Output isn't correct
19 Halted 0 ms 0 KB -