Submission #2697227

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
inline char nchar() {
	static const int bufl=1<<20;
	static char buf[bufl],*a=NULL,*b=NULL;
	return a==b && (b=(a=buf)+fread(buf,1,bufl,stdin),a==b)?EOF:*a++;
}
inline int read() {
	int x=0,f=1;
	char c=nchar();
	for (;!isdigit(c);c=nchar()) if (c=='-') f=-1;
	for (;isdigit(c);c=nchar()) x=x*10+c-'0';
	return x*f;
}
template<typename T> inline T& Min(T &x,const T &y) {return x>y?(x=y):x;}
template<typename T> inline T& Max(T &x,const T &y) {return x<y?(x=y):x;}
const int q=1e9+7;
inline int Plus(int x,int y) {return x+y>=q?(x+y-q):(x+y);}
inline int Sub(int x,int y) {return x<y?(x-y+q):(x-y);}
inline int& Pe(int &x,int y) {return x=Plus(x,y);}
const int maxn=2e5+10;
int n,L[maxn],R[maxn];
struct A {
	int x,v;
	inline bool operator < (const A &d) const {
		return x<d.x;
	}
} a[maxn];
struct range {
	int l,r;
	inline bool operator < (const range &d) const {
		return r!=d.r?(r<d.r):(l<d.l);
	}
} b[maxn];
void disc() {
	static int V[maxn];
	for (int i=1;i<=n;++i) V[i]=a[i].v;
	sort(V+1,V+n+1);
	for (int i=1;i<=n;++i) a[i].v=lower_bound(V+1,V+n+1,a[i].v)-V;
}
namespace bit {
	int n,c[maxn];
	inline void set_n(int _n) {
		n=_n+1;
	}
	inline int lowbit(int x) {
		return x&-x;
	}
	void inc(int x,int d) {
		for (++x;x<=n;x+=lowbit(x)) Pe(c[x],d);
	}
	int sum(int x) {
		int ret(0);
		for (++x;x;x-=lowbit(x)) Pe(ret,c[x]);
		return ret;
	}
	inline int sum(int x,int y) {
		return Sub(sum(y),sum(x-1));
	}
}
int main() {
	n=read();
	for (int i=1;i<=n;++i) a[i].x=read(),a[i].v=read();
	disc();
	sort(a+1,a+n+1);
	for (int i=1,tmp=INT_MIN;i<=n;++i) b[i].r=Max(tmp,a[i].v);
	for (int i=n,tmp=INT_MAX;i>0;--i) b[i].l=Min(tmp,a[i].v);
	sort(b+1,b+n+1);
	bit::set_n(n);
	bit::inc(0,1);
	for (int i=1;i<=n;++i) {
		int tmp=bit::sum(b[i].l-1,b[i].r);
		bit::inc(b[i].r,tmp);
	}
	int ans=bit::sum(n,n);
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result