fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define ld long double
  4. #define f first
  5. #define s second
  6. #define pb push_back
  7. #define eb emplace_back
  8. #define mk make_pair
  9. #define mt make_tuple
  10. #define MOD 1000000007
  11. #define fo(i,a,b) for(i=a;i<b;i++)
  12. #define foe(i,a,b) for(i=a;i<=b;i++)
  13. #define all(x) x.begin(), x.end()
  14. #define vi vector<int>
  15. #define vl vector <long long int>
  16. #define pii pair <int,int>
  17. #define pll pair <long long int, long long int>
  18. #define vpii vector< pair<int,int> >
  19. #define vpll vector < pair <long long int,long long int> >
  20. #define boost ios::sync_with_stdio(false); cin.tie(0)
  21. using namespace std;
  22. const int inf = 1e9 + 5;
  23. const ll inf64 = 1e18 + 5;
  24.  
  25. const int MAX = 1e5 + 5;
  26. int n, i;
  27. // 1-index queries
  28. struct fenwick{
  29. 	int BIT[MAX];
  30. 	void upd(int i, int val)
  31. 	{
  32. 		for(; i <= n; i += i&-i)
  33. 		BIT[i] = max(BIT[i], val);
  34. 	}
  35. 	int qry(int i)
  36. 	{
  37. 		int mx = 0;
  38. 		for(; i; i -= i&-i)
  39. 		mx = max(mx, BIT[i]);
  40. 		return mx;
  41. 	}
  42. } ft;
  43. int main()
  44. {
  45. 	boost;
  46. 	cin >> n;
  47. 	int a[n], b[n];
  48. 	fo(i, 0, n)
  49. 	cin >> a[i];
  50. 	fo(i, 0, n)
  51. 	cin >> b[i];
  52.  
  53. 	map <int, int> mp;
  54. 	fo(i, 0, n)
  55. 	mp[a[i]] = i;
  56.  
  57. 	int mx = 0;
  58. 	fo(i, 0, n) {
  59. 		if(mp.find(b[i]) != mp.end()) {
  60. 			int val = ft.qry(mp[b[i]]) + 1;
  61. 			ft.upd(mp[b[i]] + 1, val);
  62. 			mx = max(mx, val);
  63. 		}
  64. 	}
  65. 	cout << mx;
  66. }
  67.  
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lt66Su
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!