fork download
copy 
  1. import java.util.*;
  2. import java.math.*;
  3. import java.io.*;
  4. public class Main{
  5. 	public static int MAX = 100001;
  6. 	public static int c_index(int[] A,int l,int r,int k){
  7. 		int m;
  8. 		while(r-l>1){
  9. 			m = (l+r)/2;
  10. 			if(A[m]>=k){
  11. 				l = m;
  12. 			}
  13. 			else{
  14. 				r = m;
  15. 			}
  16. 		}
  17. 		return r;
  18. 	}
  19. 	public static int find_Lcs(int[] A,int size) {
  20. 		// TODO Auto-generated method stub
  21. 		int len = 1;
  22. 		int[] Table = new int[size];
  23. 		Table[0] = A[0];
  24. 		for(int i = 0;i<size;i++){
  25. 			if(A[i] < Table[0]){
  26. 				Table[0] = A[i];
  27. 			}
  28. 			else if(A[i] > Table[len-1]){
  29. 				Table[len++] = A[i];
  30. 			}
  31. 			else{
  32. 				Table[c_index(Table,-1,len-1,A[i])]=A[i];
  33. 			}
  34. 		}
  35.  
  36. 		return len;
  37.  
  38. }
  39. 	public static void main(String[] args) throws Exception{
  40. 	    Scanner sc = new Scanner(System.in);
  41. 	    int[] X = new int[100001];
  42. 	    int[] Y = new int[100001];
  43. 	    int[] C = new int[100001];
  44. 	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  45. 	    PrintWriter out = new PrintWriter(System.out,true);
  46. 	    int t = Integer.parseInt(br.readLine());
  47. 		while(t-->0){
  48. 			int n = Integer.parseInt(br.readLine());
  49. 			StringTokenizer st = new StringTokenizer(br.readLine());
  50. 			for(int i =0;i<n;i++){
  51. 				X[i] = Integer.parseInt(st.nextToken());
  52. 				C[X[i]] = i;
  53. 			}
  54. 			st = new StringTokenizer(br.readLine());
  55. 			for(int i =0;i<n;i++){
  56. 				Y[i] = Integer.parseInt(st.nextToken());
  57. 				X[i] = C[Y[i]];
  58. 			}
  59. 			out.println(find_Lcs(X,n));
  60.  
  61. 		}
  62. 		//print_Lcs(X,X.length(),Y.length());
  63. 	}
  64.  
  65.  
  66. }
Success #stdin #stdout 0.16s 321344KB
comments (?)
stdin
copy 
2
2
1 2
2 1
3
1 2 3
1 3 2
stdout
copy 
1
2
https://ideone.com/4lAcT7
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!