MXqz,快废了
查看原帖
MXqz,快废了
241817
Chancylaser楼主2021/10/31 15:02

思路:this

#include<bits/stdc++.h>
using namespace std;
int n,m1,m2;
struct gn{
	int a,b;
}f1[100005];
struct gw{
	int a,b;
}f2[100005];
bool cmp(gn x,gn y){
	return x.a<y.a;
}
bool cmp2(gw x,gw y){
	return x.a<y.a;
}
int ln[100005],k1,res[100005];
void lqfp(){
	priority_queue<pair<int,int> > lq;
	lq.push(make_pair(-f1[1].b,1));k1=1;
	ln[1]++;
	for(int i=2;i<=m1;i++){
		int x=-lq.top().first,y=lq.top().second;
		if(x<f1[i].a){
		//	cout<<x<<" "<<f1[i].a<<endl;
			ln[y]++;	
			lq.pop();
			lq.push(make_pair(-f1[i].b,y)); 
		} 
		else{
			ln[++k1]++;
			lq.push(make_pair(-f1[i].b,k1)); 	
		} 
	}
	for(int i=0;i<=n;i++){
		if(i>k1){
			res[i]=res[k1];
			continue;
		}
		res[i]=res[i-1]+ln[i];
	}
	return;
}
int k2,lw[100005],ans[100005];
void lqfp2(){
	priority_queue<pair<int,int> > lq;
	lq.push(make_pair(-f2[1].b,1));k2=1;
	lw[1]++;
	for(int i=2;i<=m2;i++){
		int x=-lq.top().first,y=lq.top().second;
		if(x<f2[i].a){
		//	cout<<x<<" "<<f2[i].a<<endl;
			lw[y]++;	
			lq.pop();
			lq.push(make_pair(-f2[i].b,y)); 
		} 
		else{
			lw[++k2]++;
			lq.push(make_pair(-f2[i].b,k2)); 	
		} 
	}
	for(int i=0;i<=n;i++){
		if(i>k2){
			ans[i]=ans[k2];
			continue;
		}
		ans[i]=ans[i-1]+lw[i];
	}
	return;
}
int zans=0;
int main(){
	scanf("%d%d%d",&n,&m1,&m2);
	for(int i=1;i<=m1;i++)
		scanf("%d%d",&f1[i].a,&f1[i].b);
	for(int i=1;i<=m2;i++)
		scanf("%d%d",&f2[i].a,&f2[i].b);	
	sort(f1+1,f1+m1+1,cmp);sort(f2+1,f2+m2+1,cmp2);
	lqfp();lqfp2();
	for(int i=0;i<=n;i++){
		int sum1=i,sum2=n-i;
		zans=max(zans,res[sum1]+ans[sum2]);
	}
	printf("%d\n",zans);
	return 0;
}

/*
3 5 4
1 5
3 8
6 10
9 14
13 18
2 11
4 15
7 17
12 16
*/
2021/10/31 15:02
加载中...