骗分骗出满分???
查看原帖
骗分骗出满分???
121813
老子是北瓜楼主2021/10/25 22:06
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

int n,m1,m2,rk[200003];
bool vis[100003];
struct plane {
	int t,val,tag;
} p1[200003],p2[200003];

bool cmp(plane pp1,plane pp2) {
	return pp1.t < pp2.t || (pp1.t == pp2.t && pp1.val < pp2.val);
} 

int count1(int k)
{
	memset(vis,0,sizeof(vis));
	int cnt=0,ans=0;
	for(int i=1; i<=2*m1; ++i)
	{
		if(p1[i].val==-1 && vis[p1[i].tag]==0) --cnt;
		if(p1[i].val==1)
		{
			if(cnt!=k){
				++cnt; ++ans;
			}
			else vis[p1[i].tag]=1;
		}
	}
	return ans;
}

int count2(int k)
{
	memset(vis,0,sizeof(vis));
	int cnt=0,ans=0;
	for(int i=1; i<=2*m2; ++i)
	{
		if(p2[i].val==-1 && vis[p2[i].tag]==0) --cnt;
		if(p2[i].val==1)
		{
			if(cnt!=k){
				++cnt; ++ans;
			}
			else vis[p2[i].tag]=1;
		}
	}
	return ans;
}

int main()
{
		
	scanf("%d%d%d",&n,&m1,&m2);
	
	int x,y; 
	for(int i=1; i<=m1; ++i){
		scanf("%d%d",&x,&y);
		p1[i*2-1].t=x; p1[i*2-1].val=1; p1[i*2-1].tag=i;
		p1[i*2].t=y; p1[i*2].val=-1; p1[i*2].tag=i;
	}
	for(int i=1; i<=m2; ++i){
		scanf("%d%d",&x,&y);
		p2[i*2-1].t=x; p2[i*2-1].val=1; p2[i*2-1].tag=i;
		p2[i*2].t=y; p2[i*2].val=-1; p2[i*2].tag=i;
	}

	sort(p1+1,p1+1+2*m1,cmp);
	sort(p2+1,p2+1+2*m2,cmp);
	
	if(n<=5000 && m1+m2<=10000)
	{
		int maxn=-1;
		for(int i=0; i<=n; ++i){
			int total=count1(i)+count2(n-i);
			if(maxn<total) maxn=total;
		}
		cout<<maxn;
	}
	else
	{
		if(n>=m1+m2){
			cout<<m1+m2;
			return 0;
		}
		int maxn=-1,maxm=-1;
		for(int i=0; i<=n; i+=n/500){
			int total=count1(i)+count2(n-i);
			if(maxn<total) {maxn=total; maxm=i;}
		}
		maxn=-1;
		for(int i=max(0,maxm-480); i<=min(n,maxm+480); ++i){
			int total=count1(i)+count2(n-i);
			if(maxn<total) maxn=total;
		}
		cout<<maxn;
	}
	
	return 0;
}
2021/10/25 22:06
加载中...