记录编号	135310	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2014]贴海报	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2014-10-31 21:47:35	内存使用	0.30 MiB

/*
	author :hzoi_ztx
	title  :[HAOI2014]贴海报
	ALG    :浮水法
*/

#include <cstdio>

#define  maxn  1001

int n , i , ans ;
int l[maxn] = {0} , r[maxn] = {0} ;
bool v[maxn] = {0} ;

int a[1001] = {0} ;

void up(int L , int R , int t ) {
	/*不知所云的浮水法*/
	if (v[i]) return ;
	while (t<=n && (l[t]>R || r[t]<L)) t ++ ;
	if (t > n) {
		ans ++ ; v[i] = true ;
	}
	if (L<l[t] && R>=l[t]) up(L,l[t]-1,t+1) ;
	if (L<=r[t] && R>r[t]) up(r[t]+1,R,t+1) ;
}

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