Submission #252659

#	Time	Username	Problem	Language	Result	Execution time	Memory
252659		Mlxa	Exhibition (JOI19_ho_t2)	C++14	100 / 100	79 ms	5624 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define x first
#define y second
using namespace std;
using ll  = long long;
#define int ll

const int N = 1e6;
int n;
int m;
pair<int, int> a[N]; // { value, size }
int b[N];

bool check(int suff) {
	int ptr = 0;
	for (int i = m - suff; i < m; ++i) {
		while (ptr < n && a[ptr].y > b[i]) {
			++ptr;
		}
		if (ptr == n) {
			return false;
		} else {
			++ptr;
		}
	}
	return true;
}

signed main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(0), cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> a[i].y >> a[i].x;
	}
	sort(a, a + n);
	for (int i = 0; i < m; ++i) {
		cin >> b[i];
	}
	sort(b, b + m);
	int lef = 0, rig = min(n, m) + 1;
	while (rig - lef > 1) {
		int mid = (lef + rig) / 2;
		if (check(mid)) {
			lef = mid;
		} else {
			rig = mid;
		}
	}
	cout << lef << "\n";
    return 0;
}

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