codeforces 1197E Culture Code

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2e5+2;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
int n;
int f[maxn],g[maxn];
struct Matryoshka{
    int in,out;
    Matryoshka(int in=0,int out=0):in(in),out(out){}
    bool operator < (const Matryoshka &x)const{
        return out<x.out;
    }
};
Matryoshka doll[maxn];
int trf[maxn],trg[maxn];
struct Binary_Indexed_Tree{
    int lowbit(int x){return x&-x;}
    void update(int x,int f,int g){
        while (x<=n){
            if (trf[x]==f) trg[x]=(trg[x]+g)%mod;
            if (trf[x]>f){
                trf[x]=f;
                trg[x]=g;
            }
            x+=lowbit(x);
        }
    }
    void query(int x,int &f,int &g){
        f=INF,g=0;
        while (x){
            if (f==trf[x]) g=(g+trg[x])%mod;
            if (f>trf[x]){
                f=trf[x];
                g=trg[x];
            }
            x-=lowbit(x);
        }
    }
};
Binary_Indexed_Tree BIT;
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&doll[i].out,&doll[i].in);
        trf[i]=INF;
    }
    sort(doll+1,doll+n+1);
    int Maxpos=0;
    for (int i=1;i<=n;i++){
        int pos=upper_bound(doll+1,doll+i+1,Matryoshka(0,doll[i].in))-doll-1;
        Maxpos=max(Maxpos,pos);
        if (!pos) BIT.update(i,f[i]=doll[i].in-doll[i].out,g[i]=1);
        else{
            BIT.query(pos,f[i],g[i]);
            f[i]+=doll[i].in-doll[i].out;
            BIT.update(i,f[i],g[i]);
        }
    }
    int ansf=INF,ansg=0;
    for (int i=Maxpos+1;i<=n;i++){
        int tmp=f[i]+doll[i].out;
        if (ansf==tmp) ansg=(ansg+g[i])%mod;
        if (ansf>tmp){
            ansf=tmp;
            ansg=g[i];
        }
    }
    printf("%d",ansg);
    return 0;
}