Submission #331756

#	Time	Username	Problem	Language	Result	Execution time	Memory
331756		MohamedAhmed04	Tenis (COCI20_tenis)	C++14	110 / 110	358 ms	12652 KiB

tenis

#include <bits/stdc++.h>

using namespace std ;

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;

const int MAX = 1e5 + 10 ;

int arr[3][MAX] , pos[3][MAX] , minidx[MAX] ;
int n ;

long long ans[MAX] ;

int state1(int i , int idx , int x)
{
	if(pos[i][x] < pos[idx][x])
		return 0 ;
	if(i < idx)
		return 1 ;
	return 2 ;
}

int state2(int i , int idx , int x)
{
	if(pos[i][x] < pos[idx][x])
		return 2 ;
	if(pos[i][x] == pos[idx][x])
		return 1 ;
	return 0 ;
}

bool check(int i , int idx , int j)
{
	int a = arr[i][j] , b = arr[idx][j] ;
	if(a == b)
		return false ;
	vector< array<int , 3> >vp ; 
	for(int k = 0 ; k <= 2 ; ++k)
		vp.push_back({min(pos[k][a] , pos[k][b]) , max(pos[k][a] , pos[k][b]) , k}) ;
	sort(vp.begin() , vp.end()) ;
	if(vp[0][2] == i)
	{
		ans[a]++ ;
		return true ;
	}
	else
		return false ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < 3 ; ++i)
	{
		for(int j = 1 ; j <= n ; ++j)
		{
			cin>>arr[i][j] ;
			pos[i][arr[i][j]] = j ;
		}
	}
	for(int i = 1 ; i <= n ; ++i)
		minidx[i] = min({pos[0][i] , pos[1][i] , pos[2][i]}) ;
	for(int i = 0 ; i < 3 ; ++i)
	{
		ordered_set< pair<int , int> >s[3][3] ;
		long long cnt = 0 ;
		for(int j = n ; j >= 1 ; --j)
		{
			int x = arr[i][j] ;
			int idx1 = 0 , idx2 = 1 ;
			if(idx1 == i)
				idx1++ ;
			if(idx2 == i || idx2 == idx1)
				idx2++ ;
			if(minidx[x] == j)
			{
				int a = state1(i , idx1 , x) , b = state1(i , idx2 , x) ;
				if(minidx[arr[idx1][j]] == j)
					cnt += check(i , idx1 , j) ;
				if(minidx[arr[idx2][j]] == j && arr[idx2][j] != arr[idx1][j])
					cnt += check(i , idx2 , j) ;
				for(int a2 = a ; a2 <= 2 ; ++a2)
				{
					for(int b2 = b ; b2 <= 2 ; ++b2)
					{
						int y = s[a2][b2].size() - s[a2][b2].order_of_key({j+1 , -1}) ; 
						cnt += y , ans[x] += y ;
					}
				}
			}
			s[state2(i , idx1 , x)][state2(i , idx2 , x)].insert({minidx[x] , x}) ;
		}
		cout<<cnt<<" " ;
	}
	cout<<"\n" ;
	for(int i = 1 ; i <= n ; ++i)
		cout<<ans[i]<<" " ;
	cout<<"\n" ;
	return 0 ;
}		

• Subtask 1: 35 / 35
• Subtask 2: 15 / 15
• Subtask 3: 60 / 60