O$n^2$过了?
查看原帖
O$n^2$过了?
384581
Meng142857楼主2021/10/29 21:50

RT

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct plane{
	int l,r;
}p1[100005],p2[100005];
bool cmp(plane a,plane b){
	if(a.l<b.l){return true;}
	if(a.l>b.l){return false;}
	if(a.r<b.r){return true;}
	else{return false;}
}
int bins(int x,int sta,int end,plane arr[]){
	if(sta==end){return sta;}
	int mid=(sta+end)/2;
	if(arr[x].r<=arr[mid].l){
		return bins(x,sta,mid,arr);
	}
	else{
		return bins(x,mid+1,end,arr);
	}
}
int n,m1,m2,w1,w2,ins[100005],outs[100005],cnt1,cnt2,s1[100005],s2[100005],maxn=-999;
bool ocp1[100005],ocp2[100005],flag;
int main(){
	//freopen("airport.in","r",stdin);
	//freopen("airport.out","w",stdout);
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;i++){
		scanf("%d%d",&p1[i].l,&p1[i].r);
	}
	for(int i=1;i<=m2;i++){
		scanf("%d%d",&p2[i].l,&p2[i].r);
	}
	sort(p1+1,p1+m1+1,cmp);
	sort(p2+1,p2+m2+1,cmp);
	for(int i=1;i<=m1;i++){
		if(ocp1[i]){continue;}
		cnt1++;
		ins[cnt1]=1;
		w1=i;
		ocp1[i]=1;
		flag=false;
		while(p1[w1].r<p1[m1].l){
			w1=bins(w1,w1,m1,p1);
			while(ocp1[w1]==1){
				w1++;
				if(w1>m1){flag=true;}
			}
			if(flag){break;}
			ocp1[w1]=1;
			ins[cnt1]++;
		}
	}
	for(int i=1;i<=m2;i++){
		if(ocp2[i]){continue;}
		cnt2++;
		outs[cnt2]=1;
		w2=i;
		ocp2[i]=1;
		flag=false;
		while(p2[w2].r<p2[m2].l){
			w2=bins(w2,w2,m2,p2);
			while(ocp2[w2]==1){
				w2++;
				if(w2>m2){flag=true;}
			}
			if(flag){break;}
			ocp2[w2]=1;
			outs[cnt2]++;
		}
	}
	s1[0]=s2[0]=0;
	for(int i=1;i<=cnt1;i++){
		s1[i]=s1[i-1]+ins[i];
	}
	for(int i=1;i<=cnt2;i++){
		s2[i]=s2[i-1]+outs[i];
	}
	for(int i=0;i<=n;i++){
		maxn=max(maxn,s1[i]+s2[n-i]);
	}
	cout<<maxn;
	return 0;
}
2021/10/29 21:50
加载中...