fork download 
  1. #include<stdio.h>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5. int tn, tree[1212121];
  6. int max(int a, int b) { if (a < b)return b; return a; }
  7. void insert_g(int w, int g) {
  8. 	for (int i = w + tn; i > 0; i /= 2) tree[i] = max(tree[i], g);
  9. }
  10. int search_g(int ss, int ee) {
  11. 	int s = ss + tn;
  12. 	int e = ee + tn;
  13. 	int res = 0;
  14. 	while (s <= e) {
  15. 		if (s % 2 == 1)res = max(res, tree[s++]);
  16. 		if (e % 2 == 0)res = max(res, tree[e--]);
  17. 		s /= 2; e /= 2;
  18. 	}
  19. 	return res;
  20. }
  21. int a[121212], b[121212], bw[121212];
  22. int main() {
  23. 	int n, i, j;
  24. 	scanf("%d", &n);
  25. 	for (tn = 1; tn < n; tn *= 2);
  26. 	for (i = 0; i < n; i++)scanf("%d", &a[i]);
  27. 	for (i = 0; i < n; i++)scanf("%d", &b[i]),bw[b[i]]=i;
  28. 	for (i = 0; i < n; i++) {
  29. 		vector<int>L;
  30. 		for (j = -4; j <= 4; j++) {
  31. 			if (a[i] + j <= 0 || a[i] + j>n)continue;
  32. 			L.push_back(bw[a[i] + j]);
  33. 		}
  34. 		sort(L.begin(), L.end());
  35. 		for (j = L.size() - 1; j >= 0; j--) {
  36. 			int next = L[j];
  37. 			insert_g(next, search_g(0, next - 1) + 1);
  38. 		}
  39. 	}
  40. 	printf("%d", tree[1]);
  41. 	return 0;
  42. }
Success #stdin #stdout 0s 4376KB
comments (?)
stdin 
6
1
2
3
4
5
6
6
5
4
3
2
1
stdout 
5
https://ideone.com/4cc5My
language:
C++ (gcc 8.3)
created:
6 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!