数据水
查看原帖
数据水
315005
White_gugu楼主2021/11/1 20:07

二分O(n^2)暴力切了 (比赛时变量打错还有25)

#include<bits/stdc++.h>
using namespace std;
struct node{
	int l,r;
}a[200200],b[200200];
int n,m1,m2;
int num1[200200],num2[200200];
int s1[200200],s2[200200];
int cnt1,cnt2,ans;
bool bz[200200];
bool cmp2(node x,node y)
{
	return x.l>y.l;
}
void fd_a(int qaq,int x,int tot)
{
	int l=1,r=qaq;
	int mid=0,an=0;
	while(l<r)
	{
		mid=(l+r)/2;
		if(a[mid].l>x)
		{
			l=mid+1;
			an=mid;
		}
		else
		r=mid;
	}
	while(bz[an]&&an>=1)
	an--;
	if(an==0)
	return;
	bz[an]=1;
	num1[tot]++;
	fd_a(an,a[an].r,tot);
}
void fd_b(int qaq,int x,int tot)
{
	int l=1,r=qaq;
	int mid=0,an=0;
	while(l<r)
	{
		mid=(l+r)/2;
		if(b[mid].l>x)
		{
			l=mid+1;
			an=mid;
		}
		else
		r=mid;
	}
	while(bz[an]&&an>=1)
	an--;
	if(an==0)
	return;
	bz[an]=1;
	num2[tot]++;
	fd_b(an,b[an].r,tot);
}
bool cmp(node x,node y)
{
	return x.l<y.l;
}
int main()
{
//	freopen("airport.in","r",stdin);
//	freopen("airport.out","w",stdout);
	scanf("%d %d %d",&n,&m1,&m2);
	for(int i=1;i<=m1;i++)
	scanf("%d %d",&a[i].l,&a[i].r);
	for(int i=1;i<=m2;i++)
	scanf("%d %d",&b[i].l,&b[i].r);
	sort(a+1,a+m1+1,cmp2);
	sort(b+1,b+m2+1,cmp2);
	for(int i=m1;i>=1;i--)
	if(!bz[i])
	{
		bz[i]=1;
		cnt1++;
		num1[cnt1]++;
		fd_a(i,a[i].r,cnt1);
	}
	memset(bz,0,sizeof(bz));
	for(int i=m2;i>=1;i--)
	if(!bz[i])
	{
		bz[i]=1;
		cnt2++;
		num2[cnt2]++;
		fd_b(i,b[i].r,cnt2);
	}
	
	for(int i=1;i<=max(cnt1,n);i++)
	s1[i]=s1[i-1]+num1[i];
	for(int i=1;i<=max(n,cnt2);i++)
	s2[i]=s2[i-1]+num2[i];
	sort(a+1,a+m1+1,cmp);
	sort(b+1,b+m2+1,cmp);
	for(int i=0;i<=n;i++)
	ans=max(ans,s1[i]+s2[n-i]);
	printf("%d\n",ans);
    return 0;
} 
2021/11/1 20:07
加载中...