forked from Ouditchya/SPOJ
-
Notifications
You must be signed in to change notification settings - Fork 0
/
XMEN.cpp
88 lines (64 loc) · 1.68 KB
/
XMEN.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// AC, ALGO : Dynamic Programming, Longest Increasing Subsequence.
/* Approach( from SPOJ Forum ) :
"relabel the numbers in wolverine array, with their corresponding indices in the magneto array.
This way the LIS of my new array with relabelled indices will be equal to the length of the LCS of
magneto and wolverine arrays."
*/
/* Some Helpful Links :
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
*/
// For any clarifications, contact me at : [email protected]
#include<cstdio>
#include<cstring>
#define MAX 100001
using namespace std ;
int CeilIndex( int A[] , int l , int r , int key )
{
int m ;
while( r - l > 1 )
{
m = l + ( r - l ) / 2 ;
( A[m] >= key ? r : l) = m ;
}
return r ;
}
int LIS_len( int A[] , int size )
{
int *tailTable = new int[size] ;
int len , i ;
memset( tailTable , 0 , sizeof( tailTable[0] ) * size ) ;
tailTable[0] = A[0] ;
len = 1 ;
for( i = 1 ; i < size ; i++ )
{
if( A[i] < tailTable[0] )
tailTable[0] = A[i] ;
else if( A[i] > tailTable[len-1] )
tailTable[len++] = A[i] ;
else
tailTable[CeilIndex( tailTable , -1 , len - 1 , A[i] )] = A[i] ;
}
delete[] tailTable ;
return len ;
}
int main( )
{
int a[MAX] , b[MAX] , c[MAX] , i , t , n ;
for( scanf("%d",&t) ; t > 0 ; t-- )
{
scanf("%d",&n) ;
for( i = 0 ; i < n ; i++ )
{
scanf("%d",&a[i]) ;
c[a[i]] = i ;
}
for( i = 0 ; i < n ; i++ )
{
scanf("%d",&b[i]) ;
a[i] = c[b[i]] ;
}
printf("%d\n",LIS_len( a , n )) ;
}
return 0 ;
}