Submission #1796555

---

Source Code Expand

#include <bits/stdc++.h>
 
using namespace std;
 
const long long MOD=1e9+7;
const double PI=3.14159265359;


int main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    vector<pair<int,int>> vp;
    for(int i=0; i<n; i++){
        int x,v;
        cin>>x>>v;
        vp.push_back({v,x});
    }
    sort(vp.begin(),vp.end());
    
    vector<pair<int,int>> ranges(n,{0,0});
    
    vector<int> LHelp(n,0);
    for(int i=1; i<n; i++){
        if(vp[i].second>vp[LHelp[i-1]].second){
            LHelp[i]=i;
        }
        else{
            LHelp[i]=LHelp[i-1];
        }
    }
    
    vector<int> RHelp(n,n-1);
    for(int i=n-2; i>=0; i--){
        if(vp[i].second<vp[RHelp[i+1]].second){
            RHelp[i]=i;
        }
        else{
            RHelp[i]=i+1;
        }
    }
    
    for(int i=0; i<n; i++){
        int l=0, r=i;
        while(l<r){
            int mid=(l+r)/2;
            if(vp[LHelp[mid]].second>=vp[i].second){
                r=mid;
            }
            else{
                l=mid+1;
            }
            
        }
        ranges[i].first=LHelp[l];
        
        l=i, r=n-1;
        while(l<r){
            int mid=(l+r)/2;
            if(vp[RHelp[mid+1]].second<=vp[i].second){
                l=mid+1;
            }
            else{
                r=mid;
            }
            
        }
        ranges[i].second=RHelp[l];
        //cout<<ranges[i].first<<" ";
    }
    
    /*
    for(auto p:ranges){
        cout<<p.first<<" "<<p.second<<endl;
    }
    */
    
    sort(ranges.begin(),ranges.end());
    vector<long long> dp(n,0), sum(n,0);
    int pos=0;
    dp[0]=1;
    sum[0]=1;
    
    for(int i=1; i<n; i++){
        dp[i]=!ranges[i].first;
        while(ranges[pos].second<ranges[i].first-1){
            pos++;
        }
        dp[i]+=sum[i-1];
        if(pos) dp[i]-=sum[pos-1];
        sum[i]=sum[i-1]+dp[i];
        dp[i]+=MOD;
        dp[i]%=MOD;
        
        sum[i]+=MOD;
        sum[i]%=MOD;
    }
    long long ans=0;
    for(int i=0; i<n; i++){
        if(ranges[i].second==n-1){
            ans+=dp[i];
            ans%=MOD;
        }
    }
    
    cout<<ans;
    
    
    
    
    
}

Submission Info

Judge Result