记录编号	278642	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	1682.[HAOI 2014]贴海报	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-07-08 11:59:07	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=20010;
struct node{
	int data,bal;
	node *lch,*rch,*prt;
	node(int d=0):data(d),bal(0),lch(NULL),rch(NULL),prt(NULL){}
};
node *root=NULL;
void insert(node*,node* =root);
node *find(int,node* =root);
void del(node*);
node *findmax(node* =root);
node *prev(node*);
node *succ(node*);
void lrot(node*);
void rrot(node*);
void qorder(node* =root);
void zorder(node* =root);
struct Event{
	bool type;//true means in,false means out
	int pos,num;
	bool operator<(const Event& x)const{
		if(pos!=x.pos)return pos<x.pos;
		if(type!=x.type)return type;
		return num>x.num;
	}
}a[maxn<<1];
int n,m=0;
bool vis[maxn]={false};
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("ha14d.in","r",stdin);
	freopen("ha14d.out","w",stdout);
#endif
	insert(new node(0));
	scanf("%*d%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].pos,&a[i+n].pos);
		a[i+n].pos++;
		a[i].num=a[i+n].num=i;
		a[i].type=true;
		a[i+n].type=false;
	}
	n<<=1;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		if(a[i].type)insert(new node(a[i].num));
		else{
			del(find(a[i].num));
			while(i<=n&&!a[i+1].type&&a[i+1].pos==a[i].pos){
				del(find(a[++i].num));
			}
		}
		vis[findmax()->data]=true;
	}
	n>>=1;
	for(int i=1;i<=n;i++)if(vis[i])m++;
	printf("%d\n",m);
	/*for(;;){
		string s;
		int x;
		cin>>s;
		if(s=="insert"){
			cin>>x;
			insert(new node(x));
		}
		else if(s=="find"){
			cin>>x;
			cout<<(find(x)?"true":"false")<<endl;
		}
		else if(s=="del"){
			cin>>x;
			del(find(x));
		}
		else if(s=="qorder"){
			qorder();
			cout<<endl;
		}
		else if(s=="zorder"){
			zorder();
			cout<<endl;
		}
		else if(s=="findmax"){
			node *y=findmax();
			if(!y)cout<<"NULL";
			else cout<<findmax()->data;
			cout<<endl;
		}
		else if(s=="query"){
			cin>>x;
			node *y=find(x);
			if(!y)cout<<"NULL";
			else{
				cout<<"data="<<y->data<<" prt=";
				if(y->prt)cout<<y->prt->data;
				else cout<<"NULL";
				cout<<" lch=";
				if(y->lch)cout<<y->lch->data;
				else cout<<"NULL";
				cout<<" rch=";
				if(y->rch)cout<<y->rch->data;
				else cout<<"NULL";
			}
			cout<<endl;
		}
		else cout<<"Bad usage\n";
	}*/
	return 0;
}
int main(){;}
int haha=MAIN();
void insert(node *x,node *rt){
	if(!root){
		root=x;
		return;
	}
	for(;;){
		if(x->data<rt->data){
			if(rt->lch)rt=rt->lch;
			else{
				rt->lch=x;
				x->prt=rt;
				break;
			}
		}
		else{
			if(rt->rch)rt=rt->rch;
			else{
				rt->rch=x;
				x->prt=rt;
				break;
			}
		}
	}
	for(;rt;x=rt,rt=rt->prt){
		if(x==rt->lch)rt->bal++;
		else rt->bal--;
		if(!rt->bal)return;
		else if(rt->bal==2){//L
			x=rt->lch;
			if(!x)continue;
			if(x->bal==1){//LL
				rt->bal=x->bal=0;
				rrot(rt);
			}
			else{//LR
				if(!x->rch)continue;
				rt->bal=x->bal=x->rch->bal=0;
				lrot(x);
				rrot(rt);
			}
			return;
		}
		else if(rt->bal==-2){//R
			x=rt->rch;
			if(!x)continue;
			if(x->bal==-1){//RR
				rt->bal=x->bal=0;
				lrot(rt);
			}
			else{//RL
				if(!x->lch)continue;
				rt->bal=x->bal=x->lch->bal=0;
				rrot(x);
				lrot(rt);
			}
			return;
		}
	}
}
node *find(int x,node *rt){
	while(rt){
		if(x==rt->data)return rt;
		if(x<rt->data)rt=rt->lch;
		else rt=rt->rch;
	}
	return NULL;
}
void del(node *x){
	if(!x)return;
	if(x->lch&&x->rch){
		node *y=prev(x);
		x->data=y->data;
		del(y);
	}
	else{
		if(x->lch&&!x->rch){
			if(!x->prt)root=x->lch;
			else{
				if(x==x->prt->lch)x->prt->lch=x->lch;
				else x->prt->rch=x->lch;
			}
			x->lch->prt=x->prt;
			delete x;
		}
		else if(!x->lch&&x->rch){
			if(!x->prt)root=x->rch;
			else{
				if(x==x->prt->lch)x->prt->lch=x->rch;
				else x->prt->rch=x->rch;
			}
			x->rch->prt=x->prt;
			delete x;
		}
		else{
			if(!x->prt){
				root=NULL;
				delete x;
			}
			else{
				if(x->prt->lch==x)x->prt->lch=NULL;
				else x->prt->rch=NULL;
				delete x;
			}
		}
		for(node *rt=x->prt;rt;rt=rt->prt){
			//if(x==rt->lch)rt->bal--;
			//else rt->bal++;
			if(rt->bal==2){//L
				x=rt->lch;
				if(!x)continue;
				if(x->bal==1){//LL
					rt->bal=x->bal=0;
					rrot(rt);
					if(rt->prt)rt->prt->bal--;
				}
				else if(x->bal==-1){//LR
					if(!x->rch)continue;
					rt->bal=x->bal=x->rch->bal=0;
					lrot(x);
					rrot(rt);
					if(rt->prt)rt->prt->bal--;
				}
				else{//LE
					rt->bal=1;
					x->bal=-1;
					rrot(rt);
				}
				rt=rt->prt;
			}
			else if(rt->bal==-2){//R
				x=rt->rch;
				if(!x)continue;
				if(x->bal==-1){//RR
					rt->bal=x->bal=0;
					lrot(rt);
					if(rt->prt)rt->prt->bal++;
				}
				else if(x->bal==1){//RL
					if(!x->lch)continue;
					rt->bal=x->bal=x->lch->bal=0;
					rrot(x);
					lrot(rt);
					if(rt->prt)rt->prt->bal++;
				}
				else{//RE
					rt->bal=-1;
					x->bal=1;
					lrot(rt);
				}
				rt=rt->prt;
			}
			
		}
	}
}
node *findmax(node* rt){
	for(;rt->rch;rt=rt->rch);
	return rt;
}
node *prev(node *x){
	if(!x->lch)return NULL;
	for(x=x->lch;x->rch;x=x->rch);
	return x;
}
node *succ(node *x){
	if(!x->rch)return NULL;
	for(x=x->rch;x->lch;x=x->lch);
	return x;
}
void lrot(node *x){
	node *y=x->rch;
	if(!y)return;
	x->rch=y->lch;
	if(y->lch)y->lch->prt=x;
	y->prt=x->prt;
	if(!x->prt)root=y;
	else if(x==x->prt->lch)x->prt->lch=y;
	else x->prt->rch=y;
	y->lch=x;
	x->prt=y;
}
void rrot(node *x){
	node *y=x->lch;
	if(!y)return;
	x->lch=y->rch;
	if(y->rch)y->rch->prt=x;
	y->prt=x->prt;
	if(!x->prt)root=y;
	else if(x==x->prt->lch)x->prt->lch=y;
	else x->prt->rch=y;
	y->rch=x;
	x->prt=y;
}
void qorder(node *x){
	printf("%d ",x->data);
	if(x->lch)qorder(x->lch);
	if(x->rch)qorder(x->rch);
}
void zorder(node *x){
	if(x->lch)zorder(x->lch);
	printf("%d ",x->data);
	if(x->rch)zorder(x->rch);
}