Submission #1207852

#TimeUsernameProblemLanguageResultExecution timeMemory
1207852algoproclubExhibition (JOI19_ho_t2)C++20
0 / 100
1 ms1864 KiB
// 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...