Submission #530414

#	Time	Username	Problem	Language	Result	Execution time	Memory
530414		leu_naut	Exhibition (JOI19_ho_t2)	C++14	100 / 100	229 ms	5308 KiB

joi2019_ho_t2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define f first
#define s second
#define ii pair <int,int>
#define pii pair <ll,ll>

const int N = 1e5;
const int MOD = 1e9 + 7;
const ll oo = 1e18;

ii a[N + 5];
int c[N + 5],n,m;

bool ok(int x)
{
    priority_queue <int, vector <int>, greater <int>> pq;
    int j = 1, tmp = 0;
    for (int i = x; i <= m; ++i) {
        while (j <= n && c[i] >= a[j].f) {
            if (a[j].s >= tmp) pq.push(a[j].s);
            ++j;
        }
        if (pq.empty()) return false;
        tmp = pq.top();
        pq.pop();
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(0);  cin.tie(0);
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i].f >> a[i].s;
    }
    for (int i = 1; i <= m; ++i) cin >> c[i];
    sort(a + 1, a + 1 + n);
    sort(c + 1, c + 1 + m);
    int l = 1, r = m, save = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (ok(mid)) {
            save = m - mid + 1;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << save << '\n';
}

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