请问下复杂度的问题(
查看原帖
请问下复杂度的问题(
25004
Barry_Wang楼主2021/11/4 22:01

RT, 感觉没啥问题 结果T到55pts(

#include <bits/stdc++.h>
using namespace std;
int n, m1, m2;
pair<int, int> p1[100005], p2[100005];
int a1[100005], a2[100005];
int main() {
	cin >> n >> m1 >> m2;
	for(int i = 1; i <= m1; ++i) {
		cin >> p1[i].first >> p1[i].second;
	}
	for(int i = 1; i <= m2; ++i) {
		cin >> p2[i].first >> p2[i].second;
	}
	sort(p1 + 1, p1 + m1 + 1);
	sort(p2 + 1, p2 + m2 + 1);
	set<pair<int, int> > st;
	set<int> s2;
	for(int i = 1; i <= n; ++i) {
		s2.insert(i);
	}
	for(int i = 1; i <= m1; ++i) {
		while(!st.empty()) {
			pair<int, int> pl = *st.begin();
			if(pl.first > p1[i].first) {
				break;
			}
			st.erase(st.begin());
			s2.insert(pl.second);
		}
		++a1[(*s2.begin())];
		st.insert(make_pair(p1[i].second, (*s2.begin())));
		s2.erase(s2.begin());
	}
	st.clear();
	s2.clear();
	for(int i = 1; i <= n; ++i) {
		s2.insert(i);
	}
	for(int i = 1; i <= m2; ++i) {
		while(!st.empty()) {
			pair<int, int> pl = *st.begin();
			if(pl.first > p2[i].first) {
				break;
			}
			st.erase(st.begin());
			s2.insert(pl.second);
		}
		++a2[(*s2.begin())];
		st.insert(make_pair(p2[i].second, (*s2.begin())));
		s2.erase(s2.begin());
	}
	for(int i = 1; i <= n; ++i) {
		a1[i] += a1[i - 1];
		a2[i] += a2[i - 1];
	}
	int ans = 0;
	for(int i = 0; i <= n; ++i) {
		ans = max(ans, a1[i] + a2[n - i]);
	}
	cout << ans << '\n';
	return 0;
}
2021/11/4 22:01
加载中...