Submission #1207852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207852		algoproclub	Exhibition (JOI19_ho_t2)	C++20	0 / 100	1 ms	1864 KiB

joi2019_ho_t2

// UUID: 4da13df1-1144-4ee2-9484-d1e773263b8f
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m;
vector <pair <int, int>> v;
vector <int> f;
vector <int> dp(2e5, 2e9);
vector <int> fi(2e5, 2e9);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	v.resize(n);
	f.resize(m);
	for (auto& p : v) cin >> p.second >> p.first;
	for (int& i : f) cin >> i;
	sort(v.begin(), v.end());
	sort(f.begin(), f.end());
	dp[0] = fi[0] = -1;
	for (auto p : v) {
		int s = p.second;
		int k = upper_bound(dp.begin(), dp.end(), s) - dp.begin();
		int l = lower_bound(f.begin(), f.end(), s) - f.begin();
		l = max(l, fi[k - 1] + 1);
		if (l < m) { dp[k] = s; fi[k] = l; }
	}
	cout << lower_bound(dp.begin(), dp.end(), 2e9) - dp.begin() - 1;
}

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