# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
59987 | baekjoon | 공장 (KOI13_factory) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.util.*;
public class KOI13_FACTORY {
static int l = 0;
static void update(int[] tree, int i, int diff) {
while (i <= l) {
tree[i] += diff;
i += (i & -i);
}
}
static int sum(int[] tree, int i) {
int ans = 0;
while (i > 0) {
ans += tree[i];
i -= (i & -i);
}
return ans;
}
static int sum(int[] tree, int l, int r) {
if (l > r) return 0;
return sum(tree, r) - sum(tree, l-1);
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i=0; i<n; i++) {
a[i] = sc.nextInt();
}
HashMap<Integer, Integer> position = new HashMap<>();
for (int i=0; i<n; i++) {
int num = sc.nextInt();
position.put(num, i+1);
}
long ans = 0;
int[] tree = new int[n+1];
l = n;
for (int i=0; i<n; i++) {
ans += (long)sum(tree, position.get(a[i])+1, n);
update(tree, position.get(a[i]), 1);
}
System.out.println(ans);
}
}