社区讨论

三分没卡掉?是兄弟就来叉我

P7913[CSP-S 2021] 廊桥分配参与者 7已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@lobcj7of
此快照首次捕获于
2023/10/29 18:46
2 年前
此快照最后确认于
2023/11/04 00:31
2 年前
查看原帖
CPP
#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;
}

回复

7 条回复,欢迎继续交流。

正在加载回复...