Submission #726092

#	Time	Username	Problem	Language	Result	Execution time	Memory
726092		vjudge1	Exhibition (JOI19_ho_t2)	Java	50 / 100	1076 ms	24592 KiB

joi2019_ho_t2

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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 0 / 50