#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 0 ;
if(pos[i][x] == pos[idx][x])
return 1 ;
return 2 ;
}
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 , idx1 , 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 ;
}
| # |
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 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
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 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
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 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
