记录编号	249640	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2014]贴海报	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2016-04-13 11:14:20	内存使用	2.70 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
const int maxn = 1e5+10;
int n, m;
inline int get_num() {
	int ans = 0;
	char tmp = getchar();
	while(tmp < '0' || tmp > '9') tmp = getchar();
	while(tmp >= '0' && tmp <= '9') {
		ans = ans*10 + tmp - '0';
		tmp = getchar();
	}
	return ans;
}

struct node {
	int tar;
	int num;
	int l;
	inline node() {}
	inline node(int tar_, int &num_, int l_) { tar = tar_, num = num_, l = l_; }
	inline bool operator < (const node &b) const {
		return num == b.num ? tar < b.tar : num > b.num;
	}
	inline bool operator == (const node &b) const {
		return num == b.num && tar == b.tar;
	}
}ns[maxn*2];

bool cmp (node a, node b) {
	return a.tar == b.tar ? a.num > b.num : a.tar < b.tar;
}

int tot;

inline void read() {
	m = get_num(); n = get_num();
	for(int i = 1; i <= n; i++) {
		ns[++tot] = node(get_num(), i, 0);
		ns[++tot] = node(get_num()+1, i, ns[tot-1].tar);
	}
} 

set<node> s;
bool app[maxn];

inline void solve() {
	sort(ns+1, ns+1+tot, cmp);
	int ans = 0;
	int now = 1;
	int now_tar = ns[1].tar;
	while(now <= tot) {
		while(now <= tot && ns[now].tar == now_tar) {
			if(ns[now].l) s.erase(node(ns[now].l, ns[now].num, 0));
			else s.insert(ns[now]);
			++now;
		}
		if(!s.empty() && !app[(*s.begin()).num]) {
			app[(*s.begin()).num] = true;
			ans++;
//			printf("num = %d\n", (*s.begin()).num);
		}
		now_tar = ns[now].tar;
	}
	printf("%d", ans);
}

int main() {
	freopen("ha14d.in", "r", stdin);
	freopen("ha14d.out", "w", stdout);
	read();
	solve();
	return 0;
}