#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>
#include <vector>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)1e18
ll MOD = 1e9+7;
void solve(){
ll n; cin >> n;
vector<pair<ll, ll>> a(n);
vector<ll> pos;
for (ll i=0; i<n; i++){
cin >> a[i].ff >> a[i].ss;
pos.push_back(a[i].ff); pos.push_back(a[i].ss);
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
ll pn=pos.size();
vector<ll> dp(pn+1); dp[0]=1;
vector<ll> pref(pn+1, 1);
ll res=0;
for (ll i=0; i<n; i++){
ll l = lower_bound(pos.begin(), pos.end(), a[i].ff)-pos.begin()+1;
ll r = lower_bound(pos.begin(), pos.end(), a[i].ss)-pos.begin()+1;
ll cres=0;
for (ll j=r; j>=l; j--){
dp[j]+=pref[j-1]; dp[j]%=MOD;
cres+=pref[j-1]; cres%=MOD;
}
res+=cres; res%=MOD;
for (ll j=1; j<=pn; j++) pref[j]=(pref[j-1]+dp[j])%MOD;
}
cout << res << ln;
}
/*
15-7=6+6-x
12
TLILII
TLILTII
TLITLTII
TLITLTLII
*/
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#ifdef LOCAL
auto start = chrono::high_resolution_clock::now();
#endif
ll testc=1;
// cin >> testc;
for (ll __c=1; __c<=testc; __c++) solve();
#ifdef LOCAL
auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
#endif
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |