oj.uz

Submission #59992

# Submission time Handle Problem Language Result Execution time Memory
59992 2018-07-23T11:57:44 Z baekjoon 공장 (KOI13_factory) Java 11
5.6 / 20
 1000 ms 55532 KB 
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

# Verdict Execution time Memory Grader output
1 Correct 169 ms 11664 KB Output is correct
2 Correct 188 ms 11664 KB Output is correct
3 Correct 202 ms 12068 KB Output is correct
4 Correct 212 ms 12916 KB Output is correct
5 Correct 302 ms 14936 KB Output is correct

Subtask #2
3.4 / 3.4

# Verdict Execution time Memory Grader output
1 Correct 278 ms 16328 KB Output is correct
2 Correct 499 ms 24860 KB Output is correct
3 Correct 496 ms 35536 KB Output is correct

Subtask #3
0 / 3.8

# Verdict Execution time Memory Grader output
1 Execution timed out 1131 ms 52700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.8

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 53484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.8

# Verdict Execution time Memory Grader output
1 Execution timed out 1012 ms 55532 KB Time limit exceeded
2 Halted 0 ms 0 KB -