Submission #721015

#	Time	Username	Problem	Language	Result	Execution time	Memory
721015		Pring	Exhibition (JOI19_ho_t2)	C++14	100 / 100	63 ms	2764 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int, int> pii;

const int MXN = 100005;
int n, m, fr[MXN], dp[MXN], lastC, ans, pre[MXN];

struct P {
    int sz, val;
    P() {
        sz = 0;
        val = 0;
    }
    P(int _sz, int _val) {
        sz = _sz;
        val = _val;
    }
} pic[MXN];

bool solve(int k) {
    int ptr = k - 1;
    for (int i = 0; i < n; i++) {
        if (pic[i].sz <= fr[ptr]) {
            if (--ptr == -1) return true;
        }
    }
    return false;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> pic[i].sz >> pic[i].val;
    for (int i = 0; i < m; i++) cin >> fr[i];
    sort(pic, pic + n, [](P &a, P &b) {
        return (a.val == b.val ? a.sz < b.sz : a.val < b.val);
    });
    sort(fr, fr + m, greater<int>());
    int l = 0, r = m + 1, mid;
    // while (l + 1 < r) {
    //     int mid = (l + r) >> 1;
    //     (solve(mid) ? l : r) = mid;
    // }
    for (l = 0, r = m + 1; l + 1 < r; (solve(mid) ? l : r) = mid) mid = (l + r) >> 1;
    cout << l << endl;
    return 0;
}

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