Submission #147236

#	Time	Username	Problem	Language	Result	Execution time	Memory
147236		joulej	Exhibition (JOI19_ho_t2)	C++17	0 / 100	3 ms	764 KiB

joi2019_ho_t2

#include <iostream>
#include <algorithm>
#include <vector>

using std::cin;
using std::cout;
using std::sort;
using std::lower_bound;
using std::upper_bound;
using std::pair;

void fast_io()
{
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
}

const int MAX_N = (int)1e5 + 777;
const int INF = (int)2e9;

int n, m;
pair<int, int> pictures[MAX_N];
int frames[MAX_N];

int a[MAX_N], dp[MAX_N];

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

	for(int i = 0; i < n; ++i)
		cin >> pictures[i].second >> pictures[i].first;

	for(int j = 0; j < m; ++j)
		cin >> frames[j];

	sort(pictures, pictures + n);
	sort(frames, frames + m);

	for(int i = 0; i < n; ++i)
		a[i] = lower_bound(frames, frames + m, pictures[i].second) - frames;

/*#ifdef __LOCAL
	cout << "a: ";

	for(int i = 0; i < n; ++i)
		cout << a[i] << " ";

	cout << "\n";
#endif*/

	for(int len = 1; len < MAX_N; ++len)
		dp[len] = INF;

	dp[0] = -INF;

	for(int i = 0; i < n; ++i)
	{
		/*for(int len = n - 1; len >= 0; --len)
		{
			int val = (dp[len] + 1 >= a[i] ? dp[len] + 1 : a[i]);

			if(val < m)
				dp[len + 1] = (val < dp[len + 1] ? val : dp[len + 1]);
		}*/

		int pos = upper_bound(dp, dp + MAX_N, a[i]) - dp;
		
		if(pos < MAX_N)
		{
			int val = (dp[pos - 1] + 1 >= a[i] ? dp[pos - 1] + 1 : a[i]);
			dp[pos] = (val < dp[pos] ? val : dp[pos]);
		}
	}

/*#ifdef __LOCAL
	cout << "dp: ";

	for(int len = 0; len <= n; ++len)
		cout << dp[len] << " ";

	cout << "\n";
#endif*/

	int answ = 0;

	while(dp[answ + 1] < m)
		++answ;

	cout << answ << "\n";
}

int main()
{
	fast_io();
	solve();

	return 0;
}

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