809D - Hitchhiking in the Baltic States - CodeForces Solution

//Man always remember love because of romance only!
#include<bits/stdc++.h>
using namespace std;
#define ls(x) tr[x].ch[0]
#define rs(x) tr[x].ch[1]
#define fa(x) tr[x].fa
#define tag(x) tr[x].tag
#define v(x) tr[x].v
#define son(x,y) tr[x].ch[y]
inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
struct node{
	int ch[2],fa;
	int v,tag;
}tr[500001];
void rotate(int x){
	int y=fa(x),z=fa(y);
	int k=(rs(y)==x);
	if(z) son(z,rs(z)==y)=x;
	fa(x)=z;
	son(y,k)=son(x,k^1);
	if(son(x,k^1)) fa(son(x,k^1))=y;
	son(x,k^1)=y;
	fa(y)=x;
}
void pushdown(int x){
	if(!tag(x)) return;
	int w=tag(x);
	if(ls(x)) v(ls(x))+=w,tag(ls(x))+=w;
	if(rs(x)) v(rs(x))+=w,tag(rs(x))+=w;
	tag(x)=0;
}
int st[500001],top;
int rt;
void splay(int x,int to){
	st[top=1]=x;
	for(int i=x;fa(i);i=fa(i)) st[++top]=fa(i);
	while(top) pushdown(st[top--]);
	while(fa(x)!=to){
		int y=fa(x),z=fa(y);
		if(z!=to) (ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
		rotate(x);
	}
	if(!to )rt=x;
}
int find(int x){
	int u=rt,res=0;
	while(u){
		pushdown(u);
		if(v(u)<x) res=u,u=rs(u);
		else u=ls(u);
	}
	return res;
}
int nex(int x){
	splay(x,0);
	x=rs(x);
	while(ls(x)) x=(ls(x));
	return x;
}
int las(int x){
	splay(x,0);
	x=ls(x);
	while(rs(x)) x=rs(x);
	return x;
}
void del(int x){
	int lst=las(x),nxt=nex(x);
	splay(lst,0);
	splay(nxt,lst);
	ls(nxt)=0;
	fa(x)=0;
}
int tot=0;
void insert(int k){
	int x=rt,fa=0;
	while(x){
		pushdown(x);
		fa=x;
		if(v(x)<=k) x=rs(x);
		else x=ls(x);
	}
	x=++tot;
	if(fa) son(fa,v(fa)<=k)=x;
	fa(x)=fa,v(x)=k;
	splay(x,0);
}
int ans=0;
void solve(int l,int r){
	int u=find(l),v=find(r),tp=nex(v);
	if(u^v){
		splay(u,0);
		splay(tp,u);
		int now=ls(tp);
		v(now)++,tag(now)++;
	}
	if(tp!=2) del(tp),ans--;
	insert(l);
	ans++;
}
int main(){
	int n=read();
	insert(-1e9-10);
	insert(+1e9+10);
	for(int i=1;i<=n;i++){
		int l=read(),r=read();
		solve(l,r);
	}
	write(ans);
	return 0;
}