三分最高可得95pts,不愧是你ccf
查看原帖
三分最高可得95pts,不愧是你ccf
371409
Dangerise楼主2024/10/8 17:14
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define il inline
#define me(a,v) memset(a,v,sizeof(a))
#define cp(a,b) memcpy(b,a,(assert(sizeof(a)==sizeof(b),sizeof(a))))
#define siz(a) ((int)a.size())
#define L(i,l,r) for(int i=l;i<=r;i++)
#define R(i,r,l) for(int i=r;i>=l;i--)
#define x first
#define y second

#define ve(a) vector<a>
#define pa(a,b) pair<a,b>
#define vep(a,b) vector<pair<a,b>>

typedef double flt;
typedef string str;

il void pc(char c) {
	putchar(c);
}
il char gc() {
	return getchar();
}
il void el() {
	pc('\n');
}
il void bp() {
	puts("Fuck ccf !");
}
il int qread() {
	int ans=0;
	char c=gc();
	bool f=0;
	while(c<'0'||c>'9') {
		if(c=='-') {
			f=1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		ans=ans*10+c-'0';
		c=getchar();
	}
	if(f) {
		return -ans;
	} else {
		return ans;
	}
}

const int N=114514*10,inf=LONG_LONG_MAX/2-114514;

struct A {
	int l,r;
};

il bool cmp(const A& x,const A& y) {
	return x.l<y.l;
}

il bool operator<(const A& x,const A& y) {
	return x.r>y.r;
}

int n,m1,m2;
A a[N],b[N];

priority_queue<A> q;
il int f(A c[],int len,int mx) {
	while(!q.empty()){
		q.pop();
	}
	int ans=0;
	L(i,1,len) {
		while(!q.empty()) {
			auto v=q.top();
			if(v.r<=c[i].l) {
				q.pop();
			}else{
				break;
			}
		}
		if(siz(q)<mx) {
			q.push(c[i]);
			ans++;
		}
	}
	return ans;
}

il int check(int x) {
	return f(a,m1,x)+f(b,m2,n-x);
}
signed main() {
  n=qread(),m1=qread(),m2=qread();
	L(i,1,m1) {
		a[i].l=qread(),a[i].r=qread();
	}
	L(i,1,m2) {
		b[i].l=qread(),b[i].r=qread();
	}
	
	sort(a+1,a+1+m1,cmp);
	sort(b+1,b+1+m2,cmp);

	int l=0,r=n;
	int ans=-inf;
	while(l<r){
		int mid1=(2*l+r)/3;
		int mid2=(l+2*r)/3;
		int v1=check(mid1),v2=check(mid2);
		if(v1>v2){
			ans=max(ans,v1);
			r=mid2-1;
		}else{
			ans=max(ans,v2);
			l=mid1+1;
		}
	}
	
	int lv=check(l),rv=check(r);
	ans=max(ans,max(lv,rv));
	printf("%lld\n",ans);
	return 0;
}
2024/10/8 17:14
加载中...