Submission #1301391

#TimeUsernameProblemLanguageResultExecution timeMemory
1301391XXBabaProBerkayTrains (BOI24_trains)C++20
100 / 100
278 ms255876 KiB
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define MP make_pair
#define PB push_back
#define all(x) begin(x), end(x)

using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;

template<typename T>
using vec = vector<T>;

template<typename T, size_t N>
using arr = array<T, N>;

const ll INF = 1e17;
const int MOD = 1e9 + 7;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;
	vec<int> d(N + 1), x(N + 1);
	vec<ll> dp(N + 1);
	vec<vec<int>> lst(N + 1);
	int sq = sqrt(N);
	for (int i = 1; i <= N; i++) {
		cin >> d[i] >> x[i];
		if (d[i] > sq || d[i] == 0) continue;
		if (x[i] <= (N - i) / d[i])
			lst[i + x[i] * d[i]].PB(i);
	}

	vec<vec<ll>> sum(sq + 1, vec<ll>(N + 1));

	dp[1] = 1;
	ll ans = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= sq; j++)
			dp[i] = (dp[i] + sum[j][i % j]) % MOD;

		ans = (ans + dp[i]) % MOD;
		if (d[i] > sq) {
			for (int t = 1; t <= x[i]; t++) {
				int y = i + t * d[i];
				if (y > N) break;
				dp[y] = (dp[y] + dp[i]) % MOD;
			}
		}
		else if (d[i])
			sum[d[i]][i % d[i]] = (sum[d[i]][i % d[i]] + dp[i]) % MOD;

		for (int j : lst[i]) {
			sum[d[j]][j % d[j]] = (sum[d[j]][j % d[j]] - dp[j] + MOD) % MOD;
		}
	}

	cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...