Submission #8396280

---

Source Code Expand

#include <bits/stdc++.h>
#define rg register
#define LL long long 

using namespace std;

const int N=200010;
const int P=1e9+7;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct node{
    int x,y;
    bool operator < (const node &bb) const {return y!=bb.y?y<bb.y:x<bb.x;}
}b[N],a[N];
int n,mx[N][20],mi[N][20],l2[N],sm=1;
int getmax(int l,int r){
    int z=l2[r-l+1];
    return max(mx[l][z],mx[r-(1<<z)+1][z]);
}
int getmin(int l,int r){
    int z=l2[r-l+1];
    return min(mi[l][z],mi[r-(1<<z)+1][z]);
}
int c[N];
void update(int x,int y){
	while(x<=n)
		c[x]=(c[x]+y)%P,x+=x&(-x);
}
int query(int x){
	int an=x>=0;
	while(x>0)
		an=(an+c[x])%P,x-=x&(-x);
	return an;
}
int main()
{
    n=read();
    for(rg int i=1;i<=n;++i) b[i].x=read(),b[i].y=read();
    sort(b+1,b+n+1);
    for(rg int i=1;i<=n;++i) mx[i][0]=mi[i][0]=b[i].x;
    for(rg int i=2;i<=n;++i) l2[i]=l2[i>>1]+1;
    for(rg int j=1;j<=l2[n];++j)
        for(rg int i=1;i+(1<<j)-1<=n;++i){
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
            mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
        }
    for(rg int i=1;i<=n;++i){
        a[i].x=a[i].y=i;
        int l=1,r=i-1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(getmax(1,mid)>b[i].x) a[i].x=mid,r=mid-1;
            else l=mid+1;
        }
        l=i+1,r=n;
        while(l<=r){
            int mid=(l+r)>>1;
            if(getmin(mid,r)<b[i].x) a[i].y=mid,l=mid+1;
            else r=mid-1;
        }
    }
    sort(a+1,a+n+1);
    for(rg int i=1;i<=n;++i){
        int ll=a[i].x,rr=a[i].y;
        int nf=(sm-query(ll-2)+P)%P;
        sm=(sm+nf)%P;
        update(rr,nf);
    }
    printf("%d\n",(sm-query(n-1)+P)%P);
    return 0;
}

Submission Info

Judge Result