Submission #969579

#	Time	Username	Problem	Language	Result	Execution time	Memory
969579		yellowtoad	Exhibition (JOI19_ho_t2)	C++17	100 / 100	107 ms	4688 KiB

joi2019_ho_t2

#include <iostream>
#include <algorithm>
#define v first
#define s second
using namespace std;

int n, m, b[100010], l, r, mid;
pair<int,int> a[100010];

bool check() {
	int pos = 1;
	for (int i = mid; i <= m; i++) {
		while ((pos <= n) && (a[pos].s > b[i])) pos++;
		if (pos > n) return 0;
		pos++;
	}
	return 1;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i].s >> a[i].v;
	for (int i = 1; i <= m; i++) cin >> b[i];
	sort(a+1,a+n+1);
	sort(b+1,b+m+1);
	l = 1; r = m;
	while (l <= r) {
		mid = (l+r)/2;
		if (check()) r = mid-1;
		else l = mid+1;
	}
	cout << m-r << endl;
}

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