记录编号	154733	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2014]贴海报	最终得分	100
用户昵称	Dijkstra	是否通过	通过
代码语言	C++	运行时间	0.026 s
提交时间	2015-03-24 14:59:12	内存使用	0.35 MiB

#include<fstream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#define MAXM 1000
using namespace std;
ifstream fin("ha14d.in");
ofstream fout("ha14d.out");
struct segment
{
	int l,r;
	int st;
};
const segment none={-1,-1};
int N,M,ans=0;
int L=0;
segment post[3*MAXM];
bool F[MAXM];
bool operator ==(segment a,segment b){return a.l==b.l&&a.r==b.r;}
void cover(int p)
{
	for(int i=0;i<p;i++)
	{
		segment x=post[p];
		segment y=post[i];
		if(y==none) continue;
		if(x.l>y.r||x.r<y.l) continue; //不相交
		if(x.l<=y.l&&x.r>=y.r) //全覆盖
		{
			post[i]=none;
			continue;
		}
		if(y.l<=x.r&&y.l>=x.l) //左覆盖
		{
			y.l=x.r+1;
			post[i]=y;
			continue;
		}
		if(y.r>=x.l&&y.r<=x.r) //右覆盖
		{
			y.r=x.l-1;
			post[i]=y;
			continue;
		}
		segment z; //包含
		z.l=x.r+1;z.r=y.r;z.st=y.st;
		y.r=x.l-1;
		post[i]=y;
		post[++L]=z;
	}
}
int main()
{
	memset(F,0,sizeof(F));
	fin>>N>>M;
	segment x;
	for(int i=1;i<=M;i++)
	{
		fin>>x.l>>x.r;
		x.st=i-1;
		post[L]=x;
		cover(L);
		L++;
	}
	for(int i=0;i<L;i++) if(!(post[i]==none))F[post[i].st]=1;
	for(int i=0;i<M;i++) if(F[i]) ans++;
	fout<<ans<<endl;
	return 0;
}