oj.uz

Submission #726092

# Submission time Handle Problem Language Result Execution time Memory
726092 2023-04-18T12:53:20 Z vjudge1 Exhibition (JOI19_ho_t2) Java 11
50 / 100
 1000 ms 24592 KB 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;


// User defined Pair class

class Pair {
    int x;
    int y;

    // Constructor
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
/*// class to define user defined comparator
class ArrayOfPairsSorter {

    static void sort(Pair[] arr) {
        Comparator<Pair> comparator = new Comparator<>() {
            @Override
            public int compare(Pair p1, Pair p2) {
                if (p1.y - p2.y == 0) {
                    return p1.x - p2.x;
                } else {
                    return p1.y - p2.y;
                }
            }
        };
        Arrays.sort(arr, comparator);
    }
}

class MergeSort{
    static void sort(Pair[] arr) {
        while
    }

    static void breaker(Pair[] arr){

    }


    static void merge(Pair[] arr1, Pair[] arr2, Pair[] temp) {
        while (arr1.length > 0 && arr2.length > 0) {
            if (arr1[0].y < arr2[0].y){
                temp
            } else if (arr1[0].y > arr2[0].y) {

            } else {

            }
        }
    }
}*/


class SortTest {
    public static void mergeSort(Pair[] elements) {
        int n = elements.length;
        Pair[] temp = new Pair[n];
        mergeSortHelper(elements, 0, n - 1, temp);
    }

    private static void mergeSortHelper(Pair[] elements, int from, int to, Pair[] temp) {
        if (from < to) {
            int middle = (from + to) / 2;
            mergeSortHelper(elements, from, middle, temp);
            mergeSortHelper(elements, middle + 1, to, temp);
            merge(elements, from, middle, to, temp);
        }
    }

    private static void merge(Pair[] elements, int from,
                              int mid, int to, Pair[] temp) {
        int i = from;
        int j = mid + 1;
        int k = from;

        while (i <= mid && j <= to) {
            if (elements[i].y < elements[j].y) {
                temp[k] = elements[i];
                i++;
            } else if ( elements[i].y > elements[j].y){
                temp[k] = elements[j];
                j++;
            } else {
                if (elements[i].x < elements[j].x) {
                    temp[k] = elements[i];
                    i++;
                } else {
                    temp[k] = elements[j];
                    j++;
                }
            }
            k++;
        }

        while (i <= mid) {
            temp[k] = elements[i];
            i++;
            k++;
        }

        while (j <= to) {
            temp[k] = elements[j];
            j++;
            k++;
        }

        for (k = from; k <= to; k++) {
            elements[k] = temp[k];
        }
    }
}


    class joi2019_ho_t2 {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int N = scanner.nextInt();
            int M = scanner.nextInt();

            Pair[] pictures = new Pair[N];
            ArrayList<Integer> frame = new ArrayList<Integer>();

            for (int i = 0; i < N; i++) {
                pictures[i] = new Pair(scanner.nextInt(), scanner.nextInt());
            }

            for (int i = 0; i < M; i++) {
                frame.add(scanner.nextInt());
            }

            //ArrayOfPairsSorter.sort(pictures);
            SortTest.mergeSort(pictures);

            Collections.sort(frame);


            int frameCounter = M;
            for (int i = N; i > 0; i--) {
                if (frameCounter > 0) {
                    if (pictures[i - 1].x <= frame.get(frameCounter - 1)) {
                        frameCounter -= 1;
                    }
                }
            }
            System.out.println(M - frameCounter);
        }
    }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 10276 KB Output is correct
2 Correct 102 ms 10328 KB Output is correct
3 Correct 104 ms 10196 KB Output is correct
4 Correct 107 ms 10208 KB Output is correct
5 Correct 103 ms 10032 KB Output is correct
6 Correct 126 ms 10200 KB Output is correct
7 Correct 110 ms 10236 KB Output is correct
8 Correct 117 ms 10180 KB Output is correct
9 Correct 109 ms 10188 KB Output is correct
10 Correct 118 ms 10080 KB Output is correct
11 Correct 128 ms 10228 KB Output is correct
12 Correct 126 ms 10208 KB Output is correct
13 Correct 117 ms 10256 KB Output is correct
14 Correct 135 ms 10032 KB Output is correct
15 Correct 138 ms 10000 KB Output is correct
16 Correct 114 ms 10140 KB Output is correct
17 Correct 109 ms 10364 KB Output is correct
18 Correct 102 ms 10248 KB Output is correct
19 Correct 124 ms 10016 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 10276 KB Output is correct
2 Correct 102 ms 10328 KB Output is correct
3 Correct 104 ms 10196 KB Output is correct
4 Correct 107 ms 10208 KB Output is correct
5 Correct 103 ms 10032 KB Output is correct
6 Correct 126 ms 10200 KB Output is correct
7 Correct 110 ms 10236 KB Output is correct
8 Correct 117 ms 10180 KB Output is correct
9 Correct 109 ms 10188 KB Output is correct
10 Correct 118 ms 10080 KB Output is correct
11 Correct 128 ms 10228 KB Output is correct
12 Correct 126 ms 10208 KB Output is correct
13 Correct 117 ms 10256 KB Output is correct
14 Correct 135 ms 10032 KB Output is correct
15 Correct 138 ms 10000 KB Output is correct
16 Correct 114 ms 10140 KB Output is correct
17 Correct 109 ms 10364 KB Output is correct
18 Correct 102 ms 10248 KB Output is correct
19 Correct 124 ms 10016 KB Output is correct
20 Correct 314 ms 14980 KB Output is correct
21 Correct 338 ms 14788 KB Output is correct
22 Correct 302 ms 14924 KB Output is correct
23 Correct 336 ms 15036 KB Output is correct
24 Correct 345 ms 15008 KB Output is correct
25 Correct 349 ms 14908 KB Output is correct
26 Correct 307 ms 14840 KB Output is correct
27 Correct 354 ms 14980 KB Output is correct
28 Correct 317 ms 15032 KB Output is correct
29 Correct 316 ms 14772 KB Output is correct
30 Correct 325 ms 14824 KB Output is correct
31 Correct 351 ms 14876 KB Output is correct
32 Correct 282 ms 15008 KB Output is correct
33 Correct 242 ms 12484 KB Output is correct
34 Correct 290 ms 14816 KB Output is correct
35 Correct 271 ms 13984 KB Output is correct
36 Correct 312 ms 14892 KB Output is correct
37 Correct 327 ms 15160 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 10276 KB Output is correct
2 Correct 102 ms 10328 KB Output is correct
3 Correct 104 ms 10196 KB Output is correct
4 Correct 107 ms 10208 KB Output is correct
5 Correct 103 ms 10032 KB Output is correct
6 Correct 126 ms 10200 KB Output is correct
7 Correct 110 ms 10236 KB Output is correct
8 Correct 117 ms 10180 KB Output is correct
9 Correct 109 ms 10188 KB Output is correct
10 Correct 118 ms 10080 KB Output is correct
11 Correct 128 ms 10228 KB Output is correct
12 Correct 126 ms 10208 KB Output is correct
13 Correct 117 ms 10256 KB Output is correct
14 Correct 135 ms 10032 KB Output is correct
15 Correct 138 ms 10000 KB Output is correct
16 Correct 114 ms 10140 KB Output is correct
17 Correct 109 ms 10364 KB Output is correct
18 Correct 102 ms 10248 KB Output is correct
19 Correct 124 ms 10016 KB Output is correct
20 Correct 314 ms 14980 KB Output is correct
21 Correct 338 ms 14788 KB Output is correct
22 Correct 302 ms 14924 KB Output is correct
23 Correct 336 ms 15036 KB Output is correct
24 Correct 345 ms 15008 KB Output is correct
25 Correct 349 ms 14908 KB Output is correct
26 Correct 307 ms 14840 KB Output is correct
27 Correct 354 ms 14980 KB Output is correct
28 Correct 317 ms 15032 KB Output is correct
29 Correct 316 ms 14772 KB Output is correct
30 Correct 325 ms 14824 KB Output is correct
31 Correct 351 ms 14876 KB Output is correct
32 Correct 282 ms 15008 KB Output is correct
33 Correct 242 ms 12484 KB Output is correct
34 Correct 290 ms 14816 KB Output is correct
35 Correct 271 ms 13984 KB Output is correct
36 Correct 312 ms 14892 KB Output is correct
37 Correct 327 ms 15160 KB Output is correct
38 Execution timed out 1076 ms 24592 KB Time limit exceeded
39 Halted 0 ms 0 KB -