123
查看原帖
123
141342
心妍扎辫很美楼主2021/10/27 12:31
#include<iostream>
#include<algorithm>
using namespace std;
long long bm1[100001],bm2[100001],s1[100001],s2[100001];
long long n,m1,m2,f1[100001],f2[100001],ans;
struct node
{
	long long a,b;
}M1[100001],M2[100001];
long long cmp(node x,node y)
{
	return x.a<y.a;
}
long long Find(long long le,long long ri,long long fi,node p[])
{
	
	if(fi>p[ri].a)return ri+1;
	if(fi<p[le].a)return le;
	if(ri-le==1)return ri;
	long long mid=(le+ri)/2;
	if(p[mid].a>fi)return Find(le,mid,fi,p);
	else return Find(mid,ri,fi,p);
	
//	long long y=le;
//	while(y<=ri)
//	{
//		if(p[y].a>fi)return y-1;
//		y++;
//	}
	return ri+1;
}
long long Count(long long st,long long fi,long long an,node M[],long long bb[])
{
	long long x;
	x=Find(st,M[0].a,fi,M);
	if(x==M[0].a+1)return an;
	if(bb[x]==0)
	{
		bb[x]=1;
		return Count(x,M[x].b,an+1,M,bb);
	}
	else 
	{
		if(x==M[0].a)return an;
		else return Count(x+1,fi,an,M,bb);
	}
}
int main()
{
	scanf("%lld%lld%lld",&n,&m1,&m2);
	M1[0].a=m1;M2[0].a=m2;
	for(long long i=1;i<=m1;++i)
			scanf("%lld%lld",&M1[i].a,&M1[i].b);
	for(long long i=1;i<=m2;++i)
			scanf("%lld%d",&M2[i].a,&M2[i].b);
	sort(M1+1,M1+1+m1,cmp);
	sort(M2+1,M2+1+m2,cmp);
	long long y=1;
	for(long long i=1;i<=m1;++i)
	{
		while(bm1[y]==1&&y<=m1)++y;
		if(bm1[y]==0&&y<=m1)
		{
			bm1[y]=1;
			f1[i]=Count(y,M1[y].b,1,M1,bm1);
		}
		s1[i]=f1[i]+s1[i-1];
	}
	y=1;
	for(long long i=1;i<=m2;++i)
	{
		long long y=1;
		while(bm2[y]==1&&y<=m2)++y;
		if(bm2[y]==0&&y<=m2)
		{
	 	 bm2[y]=1;
		 f2[i]=Count(y,M2[y].b,1,M2,bm2);
		} 
		 s2[i]=f2[i]+s2[i-1];
	}
//	for(long long i=1;i<=n;++i)
//			printf("%d ",s1[i]);
//	prlong longf("\n");
//	for(long long i=1;i<=n;++i)
//			printf("%d ",s2[i]);
//	printf("\n");
	for(long long i=0;i<=n;++i)
			ans=max(ans,s1[i]+s2[n-i]);
	printf("%lld",ans);
}
2021/10/27 12:31
加载中...