记录编号	260776	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2014]贴海报	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2016-05-14 11:36:50	内存使用	0.44 MiB

#include<cstdio>
#include<cctype>
#include<algorithm>
#define lch(x) x<<1
#define rch(x) x<<1|1
#define prt(x) x>>1
using namespace std;
const int maxn=10005;
struct poster{
	int l,r;
}lst[maxn];
int read(){
	int x;char ch;
	while(ch=getchar(),!isdigit(ch));
	x=ch-'0';
	while(ch=getchar(),isdigit(ch))x=x*10+ch-'0';
	return x;
}
int seq[maxn*2];int top=1;
int pos(int x){
	return x>0?lst[x].l:lst[-x].r;
}
bool cmp(const int &a,const int &b){
	return pos(a)<pos(b);
}
bool seen[maxn];
int heap[maxn];int _size=1;
bool empty(){
	return _size==1;
}
void swap(int &a,int &b){
	a^=b^=a^=b;
}
void insert(int x){
	heap[_size++]=x;
	int p,rt=_size-1;;
	while((p=prt(rt))&&heap[p]<heap[rt]){
		swap(heap[p],heap[rt]);
		rt=p;
	}
}
void remove(){
	heap[0]=heap[--_size];
	if(empty())return;
	int rt=0;
	while(rch(rt)<_size){
		int flag=(heap[lch(rt)]>heap[rt]?1:0)+(heap[rch(rt)]>heap[rt]?2:0);
		if(!flag)return;
		if(flag==1){
			swap(heap[rt],heap[lch(rt)]);
			rt=lch(rt);
		}else if(flag==2){
			swap(heap[rt],heap[rch(rt)]);
			rt=rch(rt);
		}else if(heap[lch(rt)]>heap[rch(rt)]){
			swap(heap[rt],heap[lch(rt)]);
			rt=lch(rt);
		}else{
			swap(heap[rt],heap[rch(rt)]);
			rt=rch(rt);
		}
	}
	if(lch(rt)<_size&&heap[lch(rt)]>heap[rt])swap(heap[rt],heap[lch(rt)]);
}
int main(){
	freopen("ha14d.in","r",stdin);
	freopen("ha14d.out","w",stdout);
	int n;
	read();//海报墙的长度不要了 
	n=read();
	for(int i=1;i<=n;++i){
		lst[i].l=read();lst[i].r=read()+1;
		seq[top++]=i;
		seq[top++]=-i;
	}
	sort(seq+1,seq+top,cmp);
	int cnt=0;
	for(int i=0;i<top;++i){
		if(!empty()&&!seen[heap[1]]&&pos(seq[i-1])!=pos(seq[i])){
			seen[heap[1]]=true;
			cnt++;
		}
		if(seq[i]>0)insert(seq[i]);
		while(!empty()&&lst[heap[1]].r<=pos(seq[i]))remove();
	
	}
	printf("%d",cnt);
	fclose(stdin);fclose(stdout);
	return 0;
}
/*
1000 4
1 100
50 80
80 99
50 98
 
*/