This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int MOD = (int)1e9 + 7, LIM = 316, LIM2 = 316;
int N, d[100005], x[100005], dp[100005], sf[LIM2 + 5][LIM2];
vector<int> ft[LIM2 + 5][LIM2];
int ls(int x) {
return x & -x;
}
void ft_upd(vector<int> &ft, int pos, int v) {
for (; pos <= (int)ft.size(); pos += ls(pos)) {
ft[pos - 1] = (ft[pos - 1] + v) % MOD;
}
}
int ft_qry(vector<int> &ft, int pos) {
int ret = 0;
for (; pos; pos -= ls(pos)) {
ret = (ret + ft[pos - 1]) % MOD;
}
return ret;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> d[i] >> x[i];
}
for (int j = 1; j <= LIM2; j++) {
for (int k = 0; k < LIM2; k++) {
// i % j == k
// i = k + j * t (t >= 0)
// k + j * t <= N
// t <= (N - k) / j
int cnt = max(0, (N - k) / j);
ft[j][k].resize(cnt);
}
}
for (int i = N; i >= 1; i--) {
if (d[i]) {
int num_stops = min(x[i], (N - i) / d[i]);
if (num_stops <= LIM) {
for (int j = 1; j <= num_stops; j++) {
dp[i] = (dp[i] + dp[i + j * d[i]]) % MOD;
}
} else {
assert(d[i] <= LIM2);
dp[i] = ((ft_qry(ft[d[i]][i % d[i]], ft[d[i]][i % d[i]].size()) - ft_qry(ft[d[i]][i % d[i]], sf[d[i]][i % d[i]] - num_stops + 1)) % MOD + MOD) % MOD;
}
}
dp[i] = (dp[i] + 1) % MOD;
for (int j = 1; j <= LIM2; j++) {
ft_upd(ft[j][i % j], ++sf[j][i % j], dp[i]);
}
}
cout << dp[1] << '\n';
}
# | 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... |