fork download 
  1. #include<stdio.h>
  2. int a[121212], b[121212], A[121212], B[121212];
  3. int W[121212], ori[121212], w_j[121212];
  4. long long f(int s, int e) {
  5. 	if (s >= e)return 0;
  6. 	int m = (s + e) / 2;
  7. 	long long res = f(s, m) + f(m + 1, e);
  8. 	int i, j, p1 = s, p2 = m + 1;
  9. 	w_j[s - 1] = m;
  10. 	for (i = s; i <= m; i++) {
  11. 		w_j[i] = w_j[i - 1];
  12. 		while (w_j[i]<e&&a[i]>a[w_j[i] + 1]) w_j[i]++;
  13. 	}
  14. 	for (i = s; i <= m; i++) res += w_j[i] - (m + 1) + 1;
  15. 	for (i = s; i <= e; i++) {
  16. 		if (p1 == m + 1 || (p2!=e+1 && a[p1]>a[p2])) b[i] = a[p2++];
  17. 		else b[i] = a[p1++];
  18. 	}
  19. 	for (i = s; i <= e; i++) a[i] = b[i];
  20. 	return res;
  21. }
  22. long long go(int *A, int *B, int n) {
  23. 	int i;
  24. 	for (i = 1; i <= n; i++) W[B[i]] = i;
  25. 	for (i = 1; i <= n; i++) a[i] = W[A[i]], ori[i] = a[i];
  26. 	long long now = f(1, n);
  27. 	long long  ans = now;
  28. 	for (i = 1; i <= n; i++) {
  29. 		now += +(n - ori[i]) - (ori[i] - 1);
  30. 		if (ans > now)ans = now;
  31. 	}
  32. 	return ans;
  33. }
  34. long long min(long long a, long long b) { if (a < b)return a; return b; }
  35. int main() {
  36. 	int n, i;
  37. 	scanf("%d", &n);
  38. 	for (i = 1; i <= n; i++) scanf("%d", &A[i]);
  39. 	for (i = 1; i <= n; i++) scanf("%d", &B[i]);
  40. 	printf("%lld", min(go(A, B, n), go(B, A, n)));
  41. 	return 0;
  42. }
Success #stdin #stdout 0s 4276KB
comments (?)
stdin 
5
5
4
1
3
2
1
3
2
5
4
stdout 
Standard output is empty
https://ideone.com/nUW4rj
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!