三分没卡掉?是兄弟就来叉我
查看原帖
三分没卡掉?是兄弟就来叉我
194761
Isenthalpic楼主2021/11/15 09:11
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct Line{int op,x,id;}c[N],d[N];
int n,m1,m2,t1,t2;
bool del[N];
bool cmp(Line A,Line B){return A.x<B.x;}
char buf[1<<24],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd(){
    int x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while (c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
int get(int x){
	int now=0,r1=0;
	memset(del,0,sizeof(del));
	for(int i=1;i<=t1;i++){
		if(c[i].op==-1){
			if(!del[c[i].id])now--;
		}
		else {
			if(now<x)now++,r1++;
			else del[c[i].id]=true;
		}
	}
	memset(del,0,sizeof(del));
	now=0;int r2=0;
	for(int i=1;i<=t2;i++){
		if(d[i].op==-1){
			if(!del[d[i].id])now--;
		}
		else {
			if(now<n-x)now++,r2++;
			else del[d[i].id]=true;
		}
	}
	return r1+r2;
}
int main(){
	//freopen("airport.in","r",stdin);
	//freopen("airport.out","w",stdout);
	n=rd();m1=rd();m2=rd();
	for(int i=1;i<=m1;i++){
		int l,r;l=rd();r=rd();
		c[++t1].op=1;c[t1].x=l;c[t1].id=i;
		c[++t1].op=-1;c[t1].x=r;c[t1].id=i;
	}
	for(int i=1;i<=m2;i++){
		int l,r;l=rd();r=rd();
		d[++t2].op=1;d[t2].x=l;d[t2].id=i;
		d[++t2].op=-1;d[t2].x=r;d[t2].id=i;
	}
	sort(c+1,c+t1+1,cmp);sort(d+1,d+t2+1,cmp);
	int l=0,r=n;
	while(l+1500<=r){
		int mid=(r-l)/3;
		int lm=l+mid,rm=r-mid;
		if(get(lm)<=get(rm))l=lm;
		else r=rm;
	}
	int ans=0;
	for(int i=max(0,l-2);i<=min(r+2,n);i++){
		int tmp=get(i);
		if(tmp>ans)ans=tmp;
	}
	cout<<ans;
	return 0;
}
2021/11/15 09:11
加载中...