Submission #1768840

---

Source Code Expand

#include<algorithm>
#include<iostream>
#include<cstdio>
#define MN 200000
#define mod 1000000007
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,L[MN+5],Mx[MN+5],f[MN+5];
pair<int,int> a[MN+5],s[MN+5];
inline int Calc(int l,int r){return (f[r]-(l?f[l-1]:0)+mod)%mod;}
int main()
{
	n=read();
	for(int i=1;i<=n;++i) a[i].first=read(),a[i].second=L[i]=read();
	sort(a+1,a+n+1);sort(L+1,L+n+1);
	for(int i=1,mx=0;i<=n;++i)
	{
		a[i].second=lower_bound(L+1,L+n+1,a[i].second)-L;
		mx=max(mx,a[i].second);Mx[i]=mx;
	}
	for(int i=n,mn=n+1;i;--i)
	{
		mn=min(mn,a[i].second);
		s[i]=make_pair(Mx[i],mn);	
	}
	sort(s+1,s+n+1);f[0]=1;
	for(int i=1,j=0;i<=n;++i)
	{
		while(j<s[i].first) ++j,f[j]=f[j-1];
		f[s[i].first]=(f[s[i].first]+Calc(s[i].second-1,s[i].first))%mod;
	}
	printf("%d\n",(f[n]-f[n-1]+mod)%mod);
	return 0;
}

Submission Info

Judge Result