O(nm)999ms过了?
查看原帖
O(nm)999ms过了?
383782
StarPatrick楼主2021/11/1 12:57
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
#define wr(x) write(x),putchar('\n')
static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
inline void read(int&r){int f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')r=(r<<3)+(r<<1)+(c^48),c=getchar();r*=f;}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10^'0');}
int n, m1, m2, tot1, tot2, sum1[100005], sum2[100005], ans;
bool book1[100005], book2[100005];
inline int max(int a,int b)
{
    return a>b?a:b;
}
struct e
{
	int l, r;
}a[100005], b[100005];
struct r
{
	int last, num;
}bri1[100005], bri2[100005];
inline bool cmp(e x, e y)
{
	return x.l<y.l;
}
int main()
{
	scanf("%d %d %d", &n, &m1, &m2);
	for (int p=1;p<=m1;++p)
	{
		read(a[p].l);
		read(a[p].r);
	}
	sort(a+1, a+m1+1, cmp);
	for (int p=1;p<=m2;++p)
	{
		read(b[p].l);
		read(b[p].r);
	}
	sort(b+1, b+m2+1, cmp);
	for (int p=1;p<=m1;++p)
	{
		bool flag = 0;
		for (int k=1;k<=tot1;++k)
		{
			if (bri1[k].last<a[p].l)
			{
				flag = 1;
				bri1[k].last = a[p].r;
				bri1[k].num++;
				break;
			}
		}
		if (!flag)
		{
			tot1++;
			bri1[tot1].last = a[p].r;
			bri1[tot1].num = 1;
		}
	}
	for (int p=1;p<=m2;++p)
	{
		bool flag = 0;
		for (int k=1;k<=tot2;++k)
		{
			if (bri2[k].last<b[p].l)
			{
				flag = 1;
				bri2[k].last = b[p].r;
				bri2[k].num++;
				break;
			}
		}
		if (!flag)
		{
			tot2++;
			bri2[tot2].last = b[p].r;
			bri2[tot2].num = 1;
		}
	}
	for (int p=1;p<=n;++p)
	{
		sum1[p] = sum1[p-1]+bri1[p].num;
		sum2[p] = sum2[p-1]+bri2[p].num;
	}
	for (int p=0;p<=n;++p)
	{
		ans = max(ans, sum1[p]+sum2[n-p]);
	}
	printf("%d", ans);
	fwrite(obuf,p3-obuf,1,stdout);
	return 0;
}
2021/11/1 12:57
加载中...