oj.uz

Submission #59988

# Submission time Handle Problem Language Result Execution time Memory
59988 2018-07-23T11:56:55 Z baekjoon 공장 (KOI13_factory) Java 11
5.6 / 20
 1000 ms 57196 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 198 ms 11780 KB Output is correct
2 Correct 202 ms 12472 KB Output is correct
3 Correct 195 ms 12472 KB Output is correct
4 Correct 253 ms 14196 KB Output is correct
5 Correct 276 ms 15380 KB Output is correct

Subtask #2
3.4 / 3.4

# Verdict Execution time Memory Grader output
1 Correct 330 ms 17296 KB Output is correct
2 Correct 453 ms 25244 KB Output is correct
3 Correct 676 ms 35992 KB Output is correct

Subtask #3
0 / 3.8

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 53268 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 1188 ms 57196 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 1082 ms 57196 KB Time limit exceeded
2 Halted 0 ms 0 KB -