20pts代码求条
查看原帖
20pts代码求条
1268479
yangdicheng2013楼主2025/7/19 16:23
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define pii pair<int, int>
#define lc(i) (i << 1)
#define rc(i) (i << 1 | 1)
#define MAXN 100005
#define MAXM 500005
const int mod = 100000007;

int n, m1, m2;
struct range {
	int a, b;
} t1[MAXN], t2[MAXN];
int res1[MAXN], res2[MAXN];

bool cmp (range a, range b) {
	return a.a < b.a;
}
void calc (range* t, int m, int* res) {
	priority_queue<pii, vector<pii>, greater<pii>> leave;
	priority_queue<int, vector<int>, greater<int>> wait;
	for (int i = 1; i <= n; i++)
		wait.push(i);
	for (int i = 1; i <= m; i++) {
		while (!leave.empty() && t[i].a >= leave.top().first) {
			wait.push(leave.top().second);
			leave.pop();
		}
		if (wait.empty())
			continue;
		int temp = wait.top();
		res[temp]++;
		leave.push({t[i].b, temp});
		wait.pop();
	}
	for (int i = 1; i <= n; i++)
		res[i] += res[i - 1];
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	cin >> n >> m1 >> m2;
	for (int i = 1; i <= m1; i++) 
		cin >> t1[i].a >> t1[i].b;
	for (int i = 1; i <= m2; i++) 
		cin >> t2[i].a >> t2[i].b;
	sort (t1 + 1, t1 + n + 1, cmp);
	sort (t2 + 1, t2 + n + 1, cmp);
	calc(t1, m1, res1);
	calc(t2, m2, res2);
	int ans = -1;
	for (int i = 0; i <= n; i++)
		ans = max(ans, res1[i] + res2[n - i]);
	cout << ans << endl;
	return 0;
}
2025/7/19 16:23
加载中...