QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#560437 | #6308. Magic | Williamxzh | WA | 5ms | 11332kb | C++23 | 2.6kb | 2024-09-12 15:45:22 | 2024-09-12 15:45:22 |
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[M],cur[M],dis[M],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[M],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,1)/*,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,1);
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11332kb
input:
5 2 3 6 7 1 9 5 10 4 8
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 5ms
memory: 10340kb
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...
output:
8134
result:
ok 1 number(s): "8134"
Test #3:
score: -100
Wrong Answer
time: 4ms
memory: 10444kb
input:
5000 3171 3172 4062 4064 4647 4651 3670 3673 7112 7114 9714 9717 3781 3789 8422 8426 457 460 5450 5454 7113 7122 6313 6320 9969 9973 828 832 6878 6892 4476 4483 892 903 251 259 6304 6315 130 134 9206 9215 2679 2686 9090 9091 8222 8228 9374 9375 2985 2989 3397 3401 4916 4918 6819 6821 883 889 2516 25...
output:
7143
result:
wrong answer 1st numbers differ - expected: '7047', found: '7143'