QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#176934 | #6308. Magic | dengziyue | WA | 1ms | 4400kb | C++14 | 2.5kb | 2023-09-12 11:07:52 | 2023-09-12 11:07:52 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define max_n 10000
#define s 0
#define t 165000
#define inf 0x3f3f3f3f
int n;
struct A{int l,r;}a[max_n+2];
int to[max_n+2];
int son[t+2][2];
int rt[max_n+2];
int ti=0;
struct E{int v,w,nx;}e[770002];
int ei=1;
int fir[t+max_n+2];
int de[t+max_n+2];
int q[t+max_n+2],ql,qr;
int ans=0;
void addedge(int u,int v,int w){
e[++ei]=(E){v,w,fir[u]}; fir[u]=ei;
e[++ei]=(E){u,0,fir[v]}; fir[v]=ei;
}
void build(int &o,int l,int r){
if(!o)o=++ti;
if(l>=r)return;
int mid=(l+r)>>1;
build(son[o][0],l,mid);
build(son[o][1],mid+1,r);
addedge(o,son[o][0],inf);
addedge(o,son[o][1],inf);
}
void upd(int &o,int o2,int l,int r,int x,int w){
o=++ti;
if(l>=r){
if(w)addedge(o,x+t,inf);
return;
}
int mid=(l+r)>>1;
if(x<=mid){
son[o][1]=son[o2][1];
upd(son[o][0],son[o2][0],l,mid,x,w);
}
else{
son[o][0]=son[o2][0];
upd(son[o][1],son[o2][1],mid+1,r,x,w);
}
addedge(o,son[o][0],inf);
addedge(o,son[o][1],inf);
}
void query(int o,int l,int r,int ql,int qr,int w){
if(!o)return;
if(ql<=l&&r<=qr){addedge(w+t,o,inf); return;}
int mid=(l+r)>>1;
if(ql<=mid)query(son[o][0],l,mid,ql,qr,w);
if(qr>mid)query(son[o][1],mid+1,r,ql,qr,w);
}
bool bfs(){
memset(de,0,sizeof(de));
de[s]=1; q[ql=qr=1]=s;
while(ql<=qr){
int u=q[ql++];
for(int i=fir[u],v;i;i=e[i].nx){
v=e[i].v;
if(e[i].w&&!de[v]){de[v]=de[u]+1; q[++qr]=v;}
}
}
return de[t];
}
int dfs(int u,int fl){
if(u==t||!fl)return fl;
int res=0;
for(int i=fir[u],v,w;i;i=e[i].nx){
v=e[i].v;
if(e[i].w&&de[u]+1==de[v]){
w=dfs(v,min(fl,e[i].w));
if(w){
e[i].w-=w; e[i^1].w+=w;
fl-=w; res+=w;
}
else de[v]=0;
}
}
if(!res)de[u]=0;
return res;
}
int main(){
#ifdef dzy
freopen("QOJ6308_1.in","r",stdin);
// freopen("QOJ6308_1.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d%d",&a[i].l,&a[i].r);
memset(fir,0,sizeof(fir));
memset(to,0,sizeof(to));
for(int i=1;i<=n;++i){addedge(s,a[i].l+t,1); addedge(a[i].r+t,t,1);}
for(int i=1;i<=n;++i)to[a[i].l]=a[i].r;
build(rt[n*2+1],1,n*2);
for(int i=n*2;i>=1;--i){
if(to[i]){
if(i+1<=to[i]-1)query(rt[i+1],1,n*2,i+1,to[i]-1,i);
upd(rt[i],rt[i+1],1,n*2,to[i],0);
}
else upd(rt[i],rt[i+1],1,n*2,i,1);
}
printf("ti=%d ei=%d\n",ti,ei);
while(bfs())ans+=dfs(s,inf);
printf("%d\n",n*2-ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4400kb
input:
5 2 3 6 7 1 9 5 10 4 8
output:
ti=61 ei=211 9
result:
wrong output format Expected integer, but "ti=61" found