记录编号	127409	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2014]贴海报	最终得分	100
用户昵称	奶猹	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2014-10-15 17:51:36	内存使用	0.30 MiB

#include<cstdio>
int m,n;
int x[1001],y[1001];
int b[1001];
int ans=1;
void init();
void work(int ,int ,int ,int );
void outit();
int main()
{
	freopen("ha14d.in","r",stdin);
	freopen("ha14d.out","w",stdout);
	init();
	outit();
	return 0;
}
void init()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		y[i]++;
	}
	for(int i=n-1;i>=1;i--)
	work(x[i],y[i],i+1,i);
}
void work(int l,int r,int t,int d)
{
	if(b[d])return ;
	while(t<=n&&(l>=y[t]||r<=x[t]))t++;
	if(t>n)
	{
		ans++;
		b[d]=1;
		return ;
	}
	if(l<x[t]&&r>x[t])
	work(l,x[t],t+1,d);
	if(r>y[t]&&l<y[t])
	work(y[t],r,t+1,d);
}
void outit()
{
	printf("%d\n",ans);
}