QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#560428 | #6308. Magic | Williamxzh | RE | 2ms | 8668kb | C++23 | 2.6kb | 2024-09-12 15:42:38 | 2024-09-12 15:42:39 |
Judging History
answer
#include <bits/stdc++.h>
#define il inline
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=10005,M=2e5+5,inf=1e9;
int n,vis[N],head[N],cur[N],dis[N],tot=1;pii a[N];
int cnt;
struct node{
int to,nxt,v;
il node(){to=nxt=0,v=0;}
}e[M];
il void add(int x,int y,int z){e[++tot].to=y,e[tot].nxt=head[x],e[tot].v=z,head[x]=tot;}
il void adde(int x,int y,int z){add(x,y,z),add(y,x,0);}
int q[N],hh,tt;
il int bfs(){
int x,y,z;for(int i=1;i<=n*2+2+cnt;++i) dis[i]=inf,cur[i]=head[i];
dis[n*2+1]=0,hh=1,tt=0,q[++tt]=n*2+1;
while(hh<=tt){
x=q[hh++];if(x==n*2+2) return 1;
for(int i=head[x];i;i=e[i].nxt){
y=e[i].to;
if(dis[y]==inf && e[i].v>0) dis[y]=dis[x]+1,q[++tt]=y;
}
}return 0;
}
int dfs(int x,int sum){
if(x==n*2+2) return sum;
int y,z,ret=0;
for(int i=cur[x];i && sum>0;i=e[i].nxt){
y=e[i].to,cur[x]=i;
if(e[i].v>0 && dis[y]==dis[x]+1){
z=dfs(y,min(sum,int(e[i].v)));if(!z) dis[y]=inf;
e[i].v-=z,e[i^1].v+=z,sum-=z,ret+=z;
}
}return ret;
}
il int dinic(){
int ret=0;
while(bfs()) ret+=dfs(n*2+1,inf);
return ret;
}
struct B{
int ls,rs,v;
il B(){ls=rs=v=0;}
}t[M];int rt[N];
void update(int lst,int fath,int &x,int l,int r,int p){
if(!x) x=++cnt;
if(l==r){adde(fath+n*2+2,l,inf)/*,printf("*** %d %d\n",p,fath+n*2+2)*/;return ;}
else if(fath) adde(fath+n*2+2,x+n*2+2,inf);
int mid=(l+r)>>1;
if(p<=mid){
t[x].rs=t[lst].rs,t[x].ls=++cnt,t[t[x].ls]=t[t[lst].ls];
update(t[lst].ls,x,t[x].ls,l,mid,p);
}
else{
t[x].ls=t[lst].ls,t[x].rs=++cnt,t[t[x].rs]=t[t[lst].rs];
update(t[lst].rs,x,t[x].rs,mid+1,r,p);
}
}
void query(int x,int l,int r,int L,int R,int p){
if(!x) return ;
if(l>=L && r<=R){
//printf("***** %d %d %d %d %d %d\n",p,l,r,L,R,(l==r)?l:x+n*2+2);
adde(p,(l==r)?l:x+n*2+2,inf);
return ;
}
int mid=(l+r)>>1;
if(L<=mid) query(t[x].ls,l,mid,L,R,p);
if(R>mid) query(t[x].rs,mid+1,r,L,R,p);
}
int x,y,z,u,v,w;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d%d",&a[i].fi,&a[i].se),vis[a[i].fi]=0,vis[a[i].se]=1;
for(int i=1;i<=n*2;++i) if(!vis[i]) adde(n*2+1,i,1);else adde(i,n*2+2,1);
sort(a+1,a+1+n);
for(int i=1;i<=n;++i){
update(rt[i-1],0,rt[i],1,n*2,a[i].se);
if(a[i].se-a[i].fi>1) query(rt[i],1,n*2,a[i].fi+1,a[i].se-1,a[i].fi);
}
printf("%d",n*2-dinic());
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 8668kb
input:
5 2 3 6 7 1 9 5 10 4 8
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: -100
Runtime Error
input:
5000 7985 7987 42 46 1591 1593 407 410 6305 6306 1456 1457 5874 5875 7135 7137 7041 7046 6813 6815 8868 8871 665 666 4055 4056 9789 9796 7067 7068 4745 4746 5167 5171 1735 1737 2125 2128 1444 1447 1348 1352 6087 6090 1381 1384 1600 1601 5187 5190 2801 2802 8449 8450 9376 9377 4021 4024 2674 2676 490...