记录编号	130200	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2014]贴海报	最终得分	100
用户昵称	→震世逆空波→	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2014-10-21 21:02:35	内存使用	0.30 MiB

#include<cstdio>

using namespace std;
int l[1001],r[1001];
bool f[1001];
int n,ans=1,m;

void work(int L,int R,int t,int P)
{
	if(f[P]) return;
	while(t<=n && (L>=r[t]||R<=l[t])) t++;
	if(t>n)
	{
		ans++;
		f[P]=1;
		return;
	}
	if(L<l[t]&&R>l[t])
	{
		work(L,l[t],t+1,P);
	}
	if(R>r[t]&&L<r[t])
	{
		work(r[t],R,t+1,P);
	}
}

int main()
{
	freopen("ha14d.in","r",stdin);
	freopen("ha14d.out","w",stdout);
	
	scanf("%d%d",&m,&n);
	
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&l[i],&r[i]);
		r[i]++;
	}
	
	for(int i=n-1;i>=1;i--)
	{
		work(l[i],r[i],i+1,i);
	}
	
	printf("%d",ans);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}