45pts求条
查看原帖
45pts求条
636442
yangyang1000楼主2023/10/1 17:36
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

int n,m1,m2,used1[100005],used2[100005],ans,sum1[100005],sum2[100005];

struct node
{
	int l,r,num;
} a[100005],b[100005];

bool operator<(node a,node b)
{
	return a.r > b.r;
}

priority_queue<int> q1,q2;
priority_queue<node> aw1,aw2;

bool cmp(node a,node b)
{
	return a.l < b.l;
}

bool cmp_int(int a,int b)
{
	return a > b;
}

int main()
{
	cin >> n >> m1 >> m2;
	for(int i=1;i<=m1;i++) cin >> a[i].l >> a[i].r;
	for(int i=1;i<=m2;i++) cin >> b[i].l >> b[i].r;
	
	sort(a+1,a+m1+1,cmp);
	sort(b+1,b+m2+1,cmp);
	
	for(int i=1;i<=n;i++) q1.push(i);
	for(int i=1;i<=m1;i++)
	{
//		if(!aw1.empty()) cout << aw1.top().r << " " << a[i].l << endl;
		while(!aw1.empty() && aw1.top().r < a[i].l)
		{
			q1.push(aw1.top().num);
			aw1.pop();
//			cout << "---" << endl;
		}
		if(!q1.empty())
		{
			a[i].num = q1.top();
			used1[a[i].num]++;
			q1.pop();
			aw1.push(a[i]);
		}
	}
	
	for(int i=1;i<=n;i++) q2.push(i);
	for(int i=1;i<=m2;i++)
	{
		while(!aw2.empty() && aw2.top().r < b[i].l)
		{
			q2.push(aw2.top().num);
			aw2.pop();
//			cout << "---" << endl;
		}
		if(!q2.empty())
		{
			b[i].num = q2.top();
			used2[b[i].num]++;
			q2.pop();
			aw2.push(b[i]);
		}
	}
	
	sort(used1+1,used1+n+1,cmp_int);
	sort(used2+1,used2+n+1,cmp_int);
	
	for(int i=1;i<=n;i++) used1[i] += used1[i-1];
	for(int i=1;i<=n;i++) used2[i] += used2[i-1];
	for(int i=0;i<=n;i++) ans = max(ans,used1[i] + used2[n-i]);
	cout << ans << endl;
	return 0;
}
2023/10/1 17:36
加载中...