Submission #1063027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063027		quanmcvn	Trains (BOI24_trains)	C++17	71 / 100	2097 ms	986704 KiB

Main

#include<bits/stdc++.h>
using namespace std;

using ll = int32_t;

constexpr size_t nmax = 100000 + 15;
constexpr size_t sqrt_n = 317 + 15;
constexpr ll mod = 1'000'000'000 + 7;

void add(ll& lhs, ll rhs) {
	lhs += rhs;
	if (lhs >= mod) lhs -= mod;
}

void sub(ll& lhs, ll rhs) {
	lhs -= rhs;
	if (lhs < 0) lhs += mod;
}

ll n;
unordered_set<ll> from[nmax];
ll dp[nmax];
ll sum[sqrt_n][sqrt_n];

struct Event {
	ll type, i;
	Event() {}
	Event(ll t_, ll i_) : type(t_), i(i_) {}
};
vector<Event> events[nmax][sqrt_n];

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	cin >> n;
	ll sqrt_n_real = sqrt(n);
	// if (n >= 10000) sqrt_n_real -= 50;
	for (ll i = 1; i <= n; ++ i) {
		ll d, x; cin >> d >> x;
		if (d == 0 || x == 0) continue;
		if (d > n) continue;
		if (x > n) x = n;
		if (d > sqrt_n_real) {
			for (ll j = 1; j <= x; ++ j) {
				ll new_i = i + d * j;
				if (new_i > n) break;
				from[new_i].insert(i);
			}
		} else {
			ll l = i + d;
			ll r = i + d * (x + 1);
			if (l <= n) {
				events[l][d].emplace_back(0, i);
			}
			if (r <= n) {
				events[r][d].emplace_back(1, i);
			}
		}
	}
	dp[1] = 1;
	for (ll i = 2; i <= n; ++ i) {
		for (const auto& j : from[i]) {
			add(dp[i], dp[j]);
		}
		for (ll d = 1; d <= sqrt_n_real; ++ d) {
			for (const auto& [type, j] : events[i][d]) {
				if (type == 0) {
					add(sum[d][j % d], dp[j]);
				} else {
					sub(sum[d][j % d], dp[j]);
				}
			}
			add(dp[i], sum[d][i % d]);
		}
 	}
	ll res = 0;
	for (ll i = 1; i <= n; ++ i) {
		add(res, dp[i]);
	}
	cout << res;
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 0 / 29