Submission #59991

#	Time	Username	Problem	Language	Result	Execution time	Memory
59991		baekjoon	공장 (KOI13_factory)	Java	5.60 / 20	1214 ms	76604 KiB

factory

import java.util.*;
public class 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);
    }
}

• Subtask 1: 2.2 / 2.2
• Subtask 2: 3.4 / 3.4
• Subtask 3: 0 / 3.8
• Subtask 4: 0 / 4.8
• Subtask 5: 0 / 5.8