Submission #3019252

---

Source Code Expand

#include<bits/stdc++.h>
//#define empty (h<t)
//#define front (q[h])
//#define pop h++
//#define push(x) q[t++]=(x)
#define M 600005
#define INF 19260817
using namespace std;
int n,m; 
struct edge{int u,v,next;}e[M*14]={0}; int head[M]={0},cur[M]={0},use=0;
void add(int x,int y,int z){e[use].u=y;e[use].v=z;e[use].next=head[x];head[x]=use++;}
void ADD(int x,int y,int z){add(x,y,z); add(y,x,0);}
int dis[M]={0},S,T;
queue<int> q; 
bool bfs(){
	memset(dis,0,sizeof(dis));
	q.push(S); dis[S]=1;
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int i=head[u];~i;i=e[i].next)
		if(dis[e[i].u]==0&&e[i].v){
			dis[e[i].u]=dis[u]+1;
			q.push(e[i].u);
		}
	}
	return dis[T];
}
int dfs(int x,int flow){
	if(x==T) return flow;
	int sum=0;
	for(int i=cur[x];~i;i=e[i].next){
		if(!e[i].v) continue;
		if(dis[e[i].u]!=dis[x]+1) continue;
		int k=dfs(e[i].u,min(e[i].v,flow));
		sum+=k; e[i].v-=k;
		e[i^1].v+=k; flow-=k;
		if(!flow) return sum;
		if(e[i].v) cur[x]=i;
	}
	return sum;
}
int dinic(){
	int ans=0,k;
	while(bfs()){
		memcpy(cur,head,sizeof(cur));
		ans+=dfs(S,INF);
	}
	return ans;
}

struct seg{
	int l,r,id;
}a[M<<2]={0}; int cnt=0;
void build(int x,int l,int r){
	a[x].id=++cnt; a[x].l=l; a[x].r=r;
	if(l==r) return ADD(a[x].id,T,1);
	int mid=(l+r)>>1;
	build(x<<1,l,mid); build(x<<1|1,mid+1,r);
	ADD(a[x].id,a[x<<1].id,INF);
	ADD(a[x].id,a[x<<1|1].id,INF);
}
void updata(int x,int l,int r,int id){
	if(l<=a[x].l&&a[x].r<=r) return ADD(id,a[x].id,1);
	int mid=(a[x].l+a[x].r)>>1;
	if(l<=mid) updata(x<<1,l,r,id);
	if(mid<r) updata(x<<1|1,l,r,id);
}

int main(){
	memset(head,-1,sizeof(head));
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++) ADD(S,i,1);
	cnt=m; T=++cnt; build(1,1,n);
	for(int i=1;i<=m;i++){
		int l,r; scanf("%d%d",&l,&r);
		if(1<=l) 
		updata(1,1,l,i);
		if(r<=n) 
		updata(1,r,n,i);
	}
	if(cnt>40000) 
	printf("%d\n",max(0,m-n));
	else cout<<m-dinic()<<endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:71:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&m,&n);
                     ^
./Main.cpp:75:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int l,r; scanf("%d%d",&l,&r);
                               ^

Judge Result