nlogn 怎么T 了
查看原帖
nlogn 怎么T 了
212833
EEchoyukii楼主2021/10/24 12:52
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>

using namespace std;
inline int read(){
	register int x=0,f=0,ch=getchar();
	while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
	return f?-x:x;
}
const int MAX=1e5+5;
int n,m1,m2;
struct E{
	int l,r;
	inline bool operator < (const E &a)const {
		return l<a.l;
	}
}A[MAX],B[MAX];
set<int>S;
map<int,int>M;
int vis[MAX],cnt[MAX],pre[MAX],suf[MAX];
signed main(){
	n=read(),m1=read(),m2=read();
	for(register int i=1;i<=m1;++i)
		A[i].l=read(),A[i].r=read();
	for(register int i=1;i<=m2;++i)
		B[i].l=read(),B[i].r=read();
	sort(A+1,A+1+m1);
	sort(B+1,B+1+m2);
	
	
	int idx=0;
	for(register int i=1;i<=m1;++i)S.insert(A[i].l),M[A[i].l]=i;
	for(register int i=1;i<=m1;++i){
		set<int>::iterator it=lower_bound(S.begin(),S.end(),A[i].r);
		if(it!=S.end()){
			int pos=*it;pos=M[pos];
			if(!vis[i]){
				vis[i]=vis[pos]=++idx;
				cnt[idx]+=2;
			}else {
				vis[pos]=vis[i];
				cnt[vis[i]]++;
			}
			S.erase(it);
		}else {
			if(!vis[i]){
				vis[i]=++idx;
				cnt[idx]++;
			}
		}
		set<int>::iterator itt=S.find(A[i].l);
		if(itt!=S.end())S.erase(itt);
	}
	for(register int i=1;i<=n;++i)pre[i]=pre[i-1]+cnt[i];
	
	S.clear();M.clear();
	memset(cnt,0,sizeof(cnt));
	memset(vis,0,sizeof(vis));
	idx=0;	

	for(register int i=1;i<=m2;++i)S.insert(B[i].l),M[B[i].l]=i;
	for(register int i=1;i<=m2;++i){
		set<int>::iterator it=lower_bound(S.begin(),S.end(),B[i].r);
		
		if(it!=S.end()){
			int pos=*it;pos=M[pos];
			if(!vis[i]){
				vis[i]=vis[pos]=++idx;
				cnt[idx]+=2;
			}else {
				vis[pos]=vis[i];
				cnt[vis[i]]++;
			}
			S.erase(it);
		}else {
			if(!vis[i]){
				vis[i]=++idx;
				cnt[idx]++;
			}
		}
		set<int>::iterator itt=S.find(B[i].l);
		if(itt!=S.end())S.erase(itt);
	}
	for(register int i=1;i<=n;++i)suf[i]=suf[i-1]+cnt[i];
	
	
//	return 0;
	
	int ans=0;
	for(register int i=0;i<=n;++i)ans=max(ans,pre[i]+suf[n-i]);
	printf("%d\n",ans);
	return 0;
}

2021/10/24 12:52
加载中...