제출 #1255226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255226		vampirr	Exhibition (JOI19_ho_t2)	Java	0 / 100	84 ms	13240 KiB

joi2019_ho_t2

import java.util.*;

public class joi2019_ho_t2 {
    static class Picture {
        int size, value;
        Picture(int s, int v) {
            size = s;
            value = v;
        }
    }

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

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

        int[] frames = new int[M];
        for (int i = 0; i < M; i++) frames[i] = in.nextInt();

        Arrays.sort(frames);
        Arrays.sort(pictures, Comparator.comparingInt(p -> p.size));

        ArrayList<Integer> values = new ArrayList<>();
        int picIdx = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int frame : frames) {
            while (picIdx < N && pictures[picIdx].size <= frame) {
                heap.add(pictures[picIdx].value);
                picIdx++;
            }
            if (!heap.isEmpty()) {
                values.add(heap.poll());
            }
        }
        ArrayList<Integer> lnds = new ArrayList<>();
        for (int val : values) {
            int pos = upperBound(lnds, val);
            if (pos == lnds.size()) lnds.add(val);
            else lnds.set(pos, val);
        }

        System.out.println(lnds.size());
    }

    static int upperBound(ArrayList<Integer> list, int val) {
        int l = 0, r = list.size();
        while (l < r) {
            int m = (l + r) / 2;
            if (list.get(m) > val) r = m;
            else l = m + 1;
        }
        return l;
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50