95 pts 求助(加了 <=)
查看原帖
95 pts 求助(加了 <=)
637796
Xy_top楼主2023/9/2 18:20
#include <bits/stdc++.h>
#define int long long
#define For(i, a, b) for (int i = (a); i <= (b); i ++)
using namespace std;
int row[100005], cnt1[100005], cnt2[100005];
priority_queue <int, vector <int>, greater <int> > q;
int n, m1, m2;
struct Node {int x, y;} a[100005];
struct node {
	int x;
	bool operator< (const node &s) const {return a[x].y > a[s.x].y;}
};
bool cmp (Node n1, Node n2) {return n1.x < n2.x;}
priority_queue <node> q_;
void solve () {
	int ans = 0;
	cin >> n >> m1 >> m2;
	For (i, 1, n) q.push (i);
	For (i, 1, m1) cin >> a[i].x >> a[i].y;
	sort (a + 1, a + m1 + 1, cmp);
	For (i, 1, m1) {
		while (!q_.empty () && a[q_.top ().x].y < a[i].x) {
			q.push (row[q_.top ().x]);
			q_.pop ();
		}
		if (!q.empty () ) {
			row[i] = q.top ();
			++ cnt1[q.top ()];
			q.pop ();
			q_.push ({i});
		}
	}
	while (!q.empty () ) q.pop ();
	while (!q_.empty () ) q_.pop ();
	For (i, 1, n) q.push (i);
	For (i, 1, m2) cin >> a[i].x >> a[i].y;
	sort (a + 1, a + m2 + 1, cmp);
	For (i, 1, m2) {
		while (!q_.empty () && a[q_.top ().x].y < a[i].x) {
			q.push (row[q_.top ().x]);
			q_.pop ();
		}
		if (!q.empty () ) {
			row[i] = q.top ();
			++ cnt2[q.top ()];
			q.pop ();
			q_.push ({i});
		}
	}
	For (i, 1, m2) cnt2[i] += cnt2[i - 1];
	For (i, 1, m1) cnt1[i] += cnt1[i - 1];
	For (i, 0, n) ans = max (ans, cnt1[i] + cnt2[n - i]);
	cout << ans;
}
signed main () {
	ios :: sync_with_stdio (false);
	int _ = 1;
//	cin >> _;
	while (_ --) {
		solve ();
		cout << '\n';
	}
	return 0;
}
2023/9/2 18:20
加载中...