100pts民间tle一个求助
查看原帖
100pts民间tle一个求助
772909
Lovely_CCCyh___楼主2023/3/13 20:11

rt

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
struct node{
	int s,t;
}ntn[1000005],itn[1000005];
bool cmp(node x,node y)
{
	return x.s<y.s;
}
struct node2{
	int last,x;
};
vector<node2> nn,in;
int a[1000005],b[1000005];
int main()
{
	int n=read(),m1=read(),m2=read(),ans=0;
	for(int i=1;i<=m1;i++) ntn[i].s=read(),ntn[i].t=read();
	for(int i=1;i<=m2;i++) itn[i].s=read(),itn[i].t=read();
	sort(ntn+1,ntn+m1+1,cmp);
	sort(itn+1,itn+m2+1,cmp);
	for(int i=1;i<=m1;i++)
	{
		int flag=0;
		for(int j=0;j<nn.size();j++) 
			if(ntn[i].s>nn[j].last)
			{
				nn[j].last=ntn[i].t;
				nn[j].x++;
				flag=1;
				break;
			}
		if(!flag) nn.push_back(node2{ntn[i].t,1});
	}
	for(int i=1;i<=m2;i++)
	{
		int flag=0;
		for(int j=0;j<in.size();j++) 
			if(itn[i].s>in[j].last)
			{
				in[j].last=itn[i].t;
				in[j].x++;
				flag=1;
				break;
			}
		if(!flag) in.push_back(node2{itn[i].t,1});
	}
	for(int i=1;i<=n;i++)
	{
		in.push_back(node2{0,0});
		nn.push_back(node2{0,0});
	}
	for(int i=1;i<=n;i++) a[i]=a[i-1]+nn[i-1].x;
	for(int i=1;i<=n;i++) b[i]=b[i-1]+in[i-1].x;
	for(int i=0;i<=n;i++) ans=max(ans,a[i]+b[n-i]);
	printf("%d\n",ans);
	return 0;
}
2023/3/13 20:11
加载中...