#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
const int mod = 1e9 + 7;
int add(int x, int y){
return ((x % mod) + (y % mod)) % mod;
}
void testCase() {
int n;
cin >> n;
vector<pair<int, int>> v(n + 1);
vector<int> seg(n * 2, 0);
for(int i = 1; i <= n; ++i){
cin >> v[i].first >> v[i].second;
}
auto update = [&](int idx, int v) -> void {
idx += n - 1;
seg[idx] = add(v, seg[idx]);
while(idx > 1){
idx >>= 1;
seg[idx] = add(seg[idx << 1], seg[idx << 1 | 1]);
}
};
auto query = [&](int l, int r) -> int {
if(l > r) return 0;
int ans = 0;
l += n - 1, r += n - 1;
while(l <= r){
if(l & 1) ans = add(ans, seg[l ++]);
if(r & 1 ^ 1) ans = add(ans, seg[r --]);
l >>= 1, r >>= 1;
}
return add(ans, mod);
};
for(int i = 1; i <= n; ++i) update(i, 1);
for(int i = n - 1; i >= 1; --i){
update(i, query(i + 1, i + v[i].second));
}
cout << add(query(1, 1), mod) << "\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
testCase();
return 0;
}
| # | 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... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |