Submission #220159

#	Time	Username	Problem	Language	Result	Execution time	Memory
220159		anatolik	Exhibition (JOI19_ho_t2)	C++14	100 / 100	262 ms	5760 KiB

joi2019_ho_t2

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long

using namespace std;

struct pict {
	ll s;
	ll v;
	pict(){}
	pict(ll s, ll v) : s(s), v(v) {}
};

bool cmp(pict& A, pict& B) {
	if (A.v != B.v)
		return A.v < B.v;
	return A.s < B.s;
}
int n, m;

bool check(vector<pict>& arr, vector<ll>& f, int x) {
	int ind = m - x;
	int pt = 0;
	while (ind < m && pt < n) {
		if (arr[pt].s <= f[ind]) {
			ind++;
			pt++;
			continue;
		}
		pt++;
	}
	return (ind == m);
}

int main() {
	cin >> n >> m;
	vector<pict> arr(n);
	for (int i = 0; i < n; i++) {
		ll s, v;
		cin >> s >> v;
		arr[i] = { s, v };
	}
	sort(arr.begin(), arr.end(), cmp);
	vector<ll> f(m);
	for (int i = 0; i < m; i++)
		cin >> f[i];
	sort(f.begin(), f.end());
	int L = -1;
	int R = min(n, m) + 1;
	while (R - L > 1) {
		int M = (L + R) / 2;
		if (check(arr, f, M))
			L = M;
		else
			R = M;
	}
	cout << L << endl;
}

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