Submission #3019231

---

Source Code Expand

#include <cstdio>
#include <queue>
using namespace std;
const int N=200005;
const int INF=1e9;
int n,m;
int a[N][2];
inline int max(int x,int y){
	return x>y?x:y;
}
inline int min(int x,int y){
	return x<y?x:y;
}
namespace DINIC{/*{{{*/
	const int S=3*N,M=23*N;
	int flow_s,flow_t;
	int dis[S],cur[S];
	int h[S],tot;
	struct Edge{
		int v,f,next;
	}e[M*2];
	void init(int _flow_s,int _flow_t){
		flow_s=_flow_s; flow_t=_flow_t;
		tot=1;
	}
	void addEdge(int u,int v,int f){
		//printf("%d %d %d\n",u,v,f);
		e[++tot]=(Edge){v,f,h[u]}; h[u]=tot;
		e[++tot]=(Edge){u,0,h[v]}; h[v]=tot;
	}
	queue<int> q;
	bool bfs(){
		for(int i=1;i<=flow_t;i++)
			dis[i]=-1,cur[i]=h[i];
		while(!q.empty()) q.pop();
		q.push(flow_s);
		dis[flow_s]=1;
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int i=h[u],v;i;i=e[i].next)
				if(e[i].f&&dis[v=e[i].v]==-1){
					dis[v]=dis[u]+1;
					if(v==flow_t) return true;
					q.push(v);
				}
		}
		return dis[flow_t]!=-1;
	}
	int dfs(int u,int flow){
		if(u==flow_t) 
			return flow;
		int get,res=0;
		for(int i=cur[u],v;i&&flow;i=e[i].next)
			if(e[i].f&&dis[v=e[i].v]==dis[u]+1){
				get=dfs(v,min(flow,e[i].f));
				e[i].f-=get;
				e[i^1].f+=get;
				if(e[i].f) cur[u]=i;
				flow-=get;
				res+=get;
			}
		if(!res) dis[u]=-1;
		return res;
	}
	int solve(){
		int res=0;
		while(bfs())
			res+=dfs(flow_s,INF);
		return res;
	}
}/*}}}*/
namespace SEG{/*{{{*/
	const int S=N*4;
	int rt,sz;
	int ch[S][2];
	void build(int &u,int l,int r){
		u=++sz;
		if(l==r){
			DINIC::addEdge(u,DINIC::flow_t,1);
			return;
		}
		int mid=(l+r)>>1;
		build(ch[u][0],l,mid);
		build(ch[u][1],mid+1,r);
		DINIC::addEdge(u,ch[u][0],INF);
		DINIC::addEdge(u,ch[u][1],INF);
	}
	void link(int u,int l,int r,int L,int R,int v){
		if(L<=l&&r<=R){
			DINIC::addEdge(v,u,1);
			return;
		}
		int mid=(l+r)>>1;
		if(R<=mid) link(ch[u][0],l,mid,L,R,v);
		else if(mid<L) link(ch[u][1],mid+1,r,L,R,v);
		else{
			link(ch[u][0],l,mid,L,mid,v);
			link(ch[u][1],mid+1,r,mid+1,R,v);
		}
	}
}/*}}}*/
void readData(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i][0],&a[i][1]);
		a[i][0]=max(a[i][0],1);
		a[i][1]=min(a[i][1],m);
	}
}
void buildGraph(){
	for(int i=1;i<=n;i++){
		DINIC::addEdge(DINIC::flow_s,i,1);
		SEG::link(SEG::rt,1,m,1,a[i][0],i);
		SEG::link(SEG::rt,1,m,a[i][1],m,i);
	}
}
int main(){
	readData();
	DINIC::init(n+2*m+1,n+2*m+2);
	SEG::sz=n;
	SEG::build(SEG::rt,1,m);
	buildGraph();
	int match=DINIC::solve();
	printf("%d\n",n-match);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void readData()’:
./Main.cpp:104:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
./Main.cpp:106:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a[i][0],&a[i][1]);
                                  ^

Judge Result