模拟能过?
查看原帖
模拟能过?
372172
Q__A__Q楼主2022/8/13 20:55
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int ll

const int maxn=1e5+10;
const int inf=1e9+7;
int n,m1,m2,ans,d1[maxn],d2[maxn],cnt,mx1,mx2;
//queue<node> q1;
//queue<node> q2;
int vis[maxn][2];

struct node {
	int a,b;
} f[maxn],s[maxn];

inline int read() {
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}

inline void write(int x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

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

signed main() {
	freopen("airport.in","r",stdin);
	freopen("airport.out","w",stdout);
	n=read(),m1=read(),m2=read();
	for(int i=1; i<=m1; ++i)
		f[i].a=read(),f[i].b=read();//mx1=max(mx1,f[i].b);
	for(int i=1; i<=m2; ++i)
		s[i].a=read(),s[i].b=read();//mx2=max(mx2,s[i].b);
	sort(f+1,f+m1+1,cmp);
	sort(s+1,s+m2+1,cmp);
	
	cnt=1;
	memset(vis,0,sizeof(vis));
	vis[1][1]=f[1].b;
	d1[1]=1;
	for(int i=2; i<=m1; ++i) {
		int xx=f[i].a,yy=f[i].b;
		bool flag=0;
		for(int j=1; j<=cnt; ++j) {
			if(/*(xx>=vis[j][0]&&*/xx>vis[j][1]/*)*/) {
				d1[j]++;
//				cout<<j<<endl;
				vis[j][0]=xx;
				vis[j][1]=yy;
				flag=1;
				break;
			}
		}
		if(!flag) {
			cnt++;
//			cout<<cnt<<endl;
//			puts("yes1");
			d1[cnt]++;
			vis[cnt][0]=xx;
			vis[cnt][1]=yy;
		}
	}
	
	cnt=1;
	memset(vis,0,sizeof(vis));
	vis[1][1]=s[1].b;
	d2[1]=1;
	for(int i=2; i<=m2; ++i) {
		int xx=s[i].a,yy=s[i].b;
		//cout<<yy<<endl;
		bool flag=0;
		for(int j=1; j<=cnt; ++j) {
			if(/*(xx>=vis[j][0]&&*/xx>vis[j][1]/*)*/) {
				d2[j]++;
				vis[j][0]=xx;
				vis[j][1]=yy;
//				cout<<j<<' '<<vis[j][1]<<endl;
				flag=1;
				break;
			}
		}
		if(!flag) {
			cnt++;
//			puts("yes2");
			d2[cnt]++;
			vis[cnt][0]=xx;
			vis[cnt][1]=yy;
		}
	}
	for(int i=1;i<=n;++i)
		d1[i]+=d1[i-1],d2[i]+=d2[i-1];
	
//	for(int i=0;i<=n;++i)
//		cout<<d1[i]<<' '<<d2[n-i]<<endl;
//	for(int i=1;i<=n;++i) cout<<vis[i][1]<<endl;
	for(int i=0; i<=n; ++i)
		ans=max(ans,d1[i]+d2[n-i]);
	write(ans);
	return 0;
}
/*
2 4 6
20 30
40 50
21 22
41 42
1 19
2 18
3 4
5 6
7 8
9 10

4

3 5 4
1 5
3 8
6 10
9 14
13 18
2 11
4 15
7 17
12 16

7
*/
2022/8/13 20:55
加载中...