oj.uz

Submission #59991

# Submission time Handle Problem Language Result Execution time Memory
59991 2018-07-23T11:57:28 Z baekjoon 공장 (KOI13_factory) Java 11
5.6 / 20
 1000 ms 76604 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 180 ms 11420 KB Output is correct
2 Correct 188 ms 11488 KB Output is correct
3 Correct 209 ms 11828 KB Output is correct
4 Correct 273 ms 13148 KB Output is correct
5 Correct 244 ms 14636 KB Output is correct

Subtask #2
3.4 / 3.4

# Verdict Execution time Memory Grader output
1 Correct 347 ms 17804 KB Output is correct
2 Correct 493 ms 26800 KB Output is correct
3 Correct 713 ms 34720 KB Output is correct

Subtask #3
0 / 3.8

# Verdict Execution time Memory Grader output
1 Execution timed out 1042 ms 53364 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 1137 ms 53364 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 1214 ms 76604 KB Time limit exceeded
2 Halted 0 ms 0 KB -