#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 42
#endif
const int mod = 1e9 + 7;
vector<int> st;
void build(int id, int tl, int tr) {
if (tl == tr) {
st[id] = 1;
return;
}
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
build(x, tl, tm);
build(y, tm + 1, tr);
st[id] = st[x] + st[y];
}
void update(int id, int tl, int tr, int i, int v) {
if (tl == tr) {
st[id] = (st[id] + v) % mod;
return;
}
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
if (i <= tm)
update(x, tl, tm, i, v);
else
update(y, tm + 1, tr, i, v);
st[id] = st[x] + st[y];
}
int query(int id, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (r < tl || tr < l) return 0;
if (l <= tl && tr <= r) return st[id] % mod;
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
return (query(x, tl, tm, l, r) + query(y, tm + 1, tr, l, r)) % mod;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> d(n), a(n);
for (int i = 0; i < n; i++) {
cin >> d[i] >> a[i];
}
if (n <= 1e4) {
vector<int> dp(n + 1, 1);
for (int i = n - 1; i >= 0; i--) {
int x = i;
if (d[i] == 0) continue;
for (int j = 0; j < a[i]; j++) {
x += d[i];
if (x >= n) break;
dp[i] += dp[x];
if (dp[i] > mod) {
dp[i] -= mod;
}
}
}
cout << dp[0] << '\n';
return 0;
}
st.resize(4 * n);
build(0, 0, n - 1);
for (int i = n - 1; i >= 0; i--) {
int l = i + 1, r = min(n, i + a[i]);
int x = query(0, 0, n - 1, l, r);
update(0, 0, n - 1, i, x);
}
cout << query(0, 0, n - 1, 0, 0) << '\n';
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... |