数据加强警告(doge)
查看原帖
数据加强警告(doge)
68335
黄鹤不复返楼主2021/10/30 08:25

我这n*m+mlogm+O(n)都能过?

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define rg register
using namespace std;

int n,m1,m2,ans=-233,cnt;
int ho[100010],ab[100010],f[100010];
struct nod{
	int a,b;
}x1[100010],x2[100010];

bool cmp(nod x,nod y){
	return x.a<y.a;
}

int main()
{
	cin>>n>>m1>>m2;
	for(rg int i=1;i<=m1;i++) scanf("%d %d",&x1[i].a,&x1[i].b);
	for(rg int i=1;i<=m2;i++) scanf("%d %d",&x2[i].a,&x2[i].b);
	
	sort(x1+1,x1+1+m1,cmp); sort(x2+1,x2+1+m2,cmp);
	
	cnt=1; 
	for(rg int i=1;i<=m2;i++)
	 {
	 	rg int k;
	 	for(k=1;k<=cnt;k++)
	 	 if(x2[i].a>=f[k])
	 	  {
	 	  	f[k]=x2[i].b; ab[cnt]++; break;
	 	  }
	 	if(k>cnt) 
		 {
		 	cnt++; ab[cnt]=ab[cnt-1]+1; f[cnt]=x2[i].b;
		 }
		else
		 {
		 	for(int rg j=k;j<=cnt-1;j++) ab[j]++;
		 } 
	 }
	cnt=1; memset(f,0,sizeof(f));
	for(rg int i=1;i<=m1;i++)
	 {
	 	rg int k;
	 	for(k=1;k<=cnt;k++)
	 	 if(x1[i].a>=f[k])
	 	  {
	 	  	f[k]=x1[i].b; ho[cnt]++; break;
	 	  }
	 	if(k>cnt) 
		 {
		 	cnt++; ho[cnt]=ho[cnt-1]+1; f[cnt]=x1[i].b;
		 }
		else
		 {
		 	for(int rg j=k;j<=cnt-1;j++) ho[j]++;
		 } 
	 }
	if(cnt<n)
	 {
	 	for(rg int i=cnt+1;i<=n;i++) ho[i]=ho[cnt];
	 }
	
	for(rg int i=0;i<=n;i++)
	 {
	 	int j=n-i;
	 	ans=max(ans,ho[i]+ab[j]);
	 }
	printf("%d\n",ans);
	
	return 0;
}
2021/10/30 08:25
加载中...