Submission #1791289

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
	int x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define MN 200000
#define N 262144
#define MOD 1000000007
struct P{int x,y;}p[MN+5];
bool cmpx(const P&a,const P&b){return a.x<b.x;}
bool cmpy(const P&a,const P&b){return a.y<b.y;}
int t[N*2+5];
inline void InC(int&a,int b){if((a+=b)>=MOD)a-=MOD;}
inline void MiN(int&a,int b){if(b<a)a=b;}
inline void MaX(int&a,int b){if(b>a)a=b;}
void add(int k,int x,void(*rw)(int&,int)){for(k+=N;k;k>>=1)rw(t[k],x);}
int query(int l,int r,void(*rw)(int&,int))
{
	int res=t[0];
	for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1)
	{
		if(~l&1)rw(res,t[l+1]);
		if( r&1)rw(res,t[r-1]);
	}
	return res;
}
int main()
{
	int n=read(),i;
	for(i=1;i<=n;++i)p[i].x=read(),p[i].y=read();
	sort(p+1,p+n+1,cmpx);
	for(i=1;i<=n;++i)p[i].x=i;
	sort(p+1,p+n+1,cmpy);
	memset(t,40,sizeof(t));
	for(i=1;i<=n;++i)add(p[i].x,i,MiN),p[i].y=query(p[i].x,n,MiN);
	memset(t,0,sizeof(t));
	for(i=n;i;--i)add(p[i].x,i,MaX),p[i].x=query(1,p[i].x,MaX);
	sort(p+1,p+n+1,cmpy);
	memset(t,0,sizeof(t));add(0,1,InC);
	for(i=1;i<=n;++i)add(p[i].x,query(p[i].y-1,n,InC),InC);
	printf("%d",t[n+N]);
}

Submission Info

Judge Result