35pts球跳
查看原帖
35pts球跳
795344
lfxxx_楼主2024/10/19 12:27

rt

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5,V=1e5+1;
struct seg{int l,r;}a[N],b[N];
bool cmp(seg s1,seg s2){return s1.l<s2.l;}
int cnt1[N],cnt2[N];
int lst[N];
int L[N],R[N],pos[N],minn[N];
void update(int x,int d)
{
	lst[x]=d;
	minn[pos[x]]=0x3f3f3f3f;
	for(int i=L[pos[x]];i<=R[pos[x]];++i)
		minn[pos[x]]=min(minn[pos[x]],lst[i]);
}
int query(int l,int r,int v)
{
	int x=pos[l],y=pos[r];
	if(x==y)
	{
		for(int i=l;i<=r;++i)
			if(lst[i]<v)
				return i;
		return -1; 
	}
	if(minn[x]<v)
		return query(l,R[x],v);
	for(int i=x+1;i<y;++i)
		if(minn[i]<v)
			return query(L[i],R[i],v);
	return query(L[y],r,v);
}
signed main()
{
//	freopen("7913.in","r",stdin);
//	freopen("7913.out","w",stdout);
	int n,m1,m2;
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;++i)
		cin>>a[i].l>>a[i].r;
	for(int i=1;i<=m2;++i)
		cin>>b[i].l>>b[i].r;
	sort(a+1,a+m1+1,cmp);
	sort(b+1,b+m2+1,cmp);
	int t=sqrt(V);
	for(int i=1;i<=t;++i)
		L[i]=(i-1)*t+1,R[i]=i*t;
	if(R[t]<V)
	{
		++t;
		L[t]=R[t-1]+1;
		R[t]=V; 
	}
	for(int i=1;i<=t;++i)
		for(int j=L[i];j<=R[i];++j)
			pos[j]=i; 
	int cur=0,tot1=0;
	for(int i=1;i<=m1;++i)
	{
		cur=query(1,tot1,a[i].l);
		if(cur==-1)
			cur=++tot1;
//		cout<<cur<<' ';
		++cnt1[cur];
		update(cur,a[i].r);
	}
//	cout<<'\n';
	memset(lst,0,sizeof lst);
	memset(minn,0,sizeof minn);
	int tot2=0;
	cur=0;
	for(int i=1;i<=m2;++i)
	{
		cur=query(1,tot2,b[i].l);
		if(cur==-1)
			cur=++tot2;
//		cout<<cur<<' ';
		++cnt2[cur];
		update(cur,b[i].r);
	}
//	cout<<'\n';
	for(int i=1;i<=V;++i)
		cnt1[i]+=cnt1[i-1];
	for(int i=1;i<=V;++i)
		cnt2[i]+=cnt2[i-1];
	int sum=0,ans=0;
	for(int i=0;i<=n;++i)
	{
		sum=cnt1[i]+cnt2[n-i];
		ans=max(ans,sum); 
	}
	cout<<ans; 
}
2024/10/19 12:27
加载中...