社区讨论
三分没卡掉?是兄弟就来叉我
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 条回复,欢迎继续交流。
正在加载回复...