제출 #97442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97442		polyfish	Exhibition (JOI19_ho_t2)	C++14	100 / 100	83 ms	1656 KiB

joi2019_ho_t2

//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 100002;

struct picture {
	int sz, val;
};

int n, m, fr[MAX_N];
picture pic[MAX_N];

void readInput() {
	cin >> n >> m;

	for (int i=1; i<=n; ++i)
		cin >> pic[i].sz >> pic[i].val;

	for (int i=1; i<=m; ++i)
		cin >> fr[i];
}

bool check(int cnt) {
	int cur = m - cnt;

	for (int i=1; i<=n; ++i) {
		if (cur<m && pic[i].sz<=fr[cur+1])
			++cur;
	}

	return cur==m;
}

void solve() {
	sort(pic+1, pic+n+1, [](picture p1, picture p2) {
		if (p1.val!=p2.val)
			return p1.val < p2.val;
		return p1.sz < p2.sz;
	});
	// for (int i=1; i<=n; ++i)
	// 	cerr << pic[i].val << ' ';
	// cerr << '\n';

	sort(fr+1, fr+m+1);
	// PR(fr, m);

	int l = 0, r = m;

	for (int mid=(l+r)/2; mid!=l && r!=mid; mid=(l+r)/2) {
		if (check(mid))
			l = mid;
		else
			r = mid;
	}

	for (int i=r; i>=l; --i) {
		if (check(i)) {
			cout << i;
			return;
		}
	}
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".in", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	readInput();
	solve();
}

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