Submission #101695

#	Time	Username	Problem	Language	Result	Execution time	Memory
101695		KCSC	Exhibition (JOI19_ho_t2)	C++14	0 / 100	3 ms	384 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
using namespace std;

const int DIM = 100005;

int frm[DIM], stk[DIM];
pair<int, int> pic[DIM];

int main(void) {
#ifdef HOME
	freopen("exhibition.in", "r", stdin);
	freopen("exhibition.out", "w", stdout);
#endif
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> pic[i].first >> pic[i].second; }
	for (int i = 1; i <= m; ++i) {
		cin >> frm[i]; }
	sort(pic + 1, pic + n + 1);
	sort(frm + 1, frm + m + 1);
	int le1 = 1, ri1 = m; 
	while (le1 <= ri1) {
		int md1 = (le1 + ri1) >> 1, sz = 0;
		for (int i = 1; i <= n and sz < md1; ++i) {
			if (pic[i].second >= pic[stk[sz]].second and pic[i].first <= frm[m - md1 + sz + 1]) {
				stk[++sz] = i; }
			else {
				int le2 = 1, ri2 = sz;
				while (le2 <= ri2) {
					int md2 = (le2 + ri2) >> 1;
					if (pic[i].second >= pic[stk[md2 - 1]].second and pic[i].first <= frm[m - md1 + md2]) {
						le2 = md2 + 1; }
					else {
						ri2 = md2 - 1; } }
				if (ri2 != 0 and pic[stk[ri2]].second > pic[i].second) {
					stk[ri2] = i; } } }
		if (sz == md1) {
			le1 = md1 + 1; }
		else {
			ri1 = md1 - 1; } }
	cout << ri1;
	return 0; }

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