oj.uz

Submission #331756

# Submission time Handle Problem Language Result Execution time Memory
331756 2020-11-29T22:35:25 Z MohamedAhmed04 Tenis (COCI20_tenis) C++14
110 / 110
 358 ms 12652 KB 
#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.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 7 ms 748 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 7 ms 748 KB Output is correct
5 Correct 103 ms 5228 KB Output is correct
6 Correct 197 ms 7660 KB Output is correct
7 Correct 270 ms 10092 KB Output is correct
8 Correct 358 ms 12472 KB Output is correct
9 Correct 243 ms 12652 KB Output is correct
10 Correct 266 ms 12436 KB Output is correct