fork download 
  1. #include<stdio.h>
  2. struct xy {
  3. 	int x, y;
  4. 	bool operator <(const xy p) { return x < p.x; }
  5. }a[121212],temp[121212];
  6. int bw[121212],b[121212];
  7. int tree[1212121], tn;
  8. int n, k;
  9. void insert_g(int w, int g) {
  10. 	for (int i = w + tn - 1; i > 0; i /= 2)tree[i] += g;
  11. }
  12. int search_g(int ss, int ee) {
  13. 	int s = ss + tn - 1;
  14. 	int e = ee + tn - 1;
  15. 	int res = 0;
  16. 	while (s <= e) {
  17. 		if (s % 2 == 1)res += tree[s++];
  18. 		if (e % 2 == 0)res += tree[e--];
  19. 		s /= 2, e /= 2;
  20. 	}
  21. 	return res;
  22. }
  23. long long f(int s, int e) {
  24. 	if (s == e)return 0;
  25. 	int m = (s + e) / 2, i;
  26. 	long long res = f(s, m) + f(m + 1, e);
  27. 	int p1 = s, p2 = m + 1;
  28. 	for (i = s; i <= e; i++) {
  29. 		if (p2 == e + 1 || (p1 != m + 1 && a[p1] < a[p2])) {
  30. 			res += search_g(1, a[p1].y - k - 1) + search_g(a[p1].y+k+1,n);
  31. 			temp[i] = a[p1++];
  32. 		}
  33. 		else {
  34. 			insert_g(a[p2].y, 1);
  35. 			temp[i] = a[p2++];
  36. 		}
  37. 	}
  38. 	for (i = m + 1; i <= e; i++)insert_g(a[i].y, -1);
  39. 	for (i = s; i <= e; i++)a[i] = temp[i];
  40. 	return res;
  41. }
  42. int main() {
  43. 	int i, j;
  44. 	scanf("%d%d", &n, &k);
  45. 	for (tn = 1; tn < n; tn *= 2);
  46. 	for (i = 0; i < n; i++)scanf("%d", &a[i].y);
  47. 	for (i = 0; i < n; i++)scanf("%d", &b[i]), bw[b[i]] = i;
  48. 	for (i = 0; i < n; i++)a[i].x = bw[a[i].y];
  49. 	printf("%lld", f(0, n - 1));
  50. 	return 0;
  51. }
Success #stdin #stdout 0s 4288KB
comments (?)
stdin 
4 1
4
3
2
1
1
4
2
3
stdout 
2
https://ideone.com/Jmlreq
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!