Submission #1063047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063047		quanmcvn	Trains (BOI24_trains)	C++17	50 / 100	89 ms	7508 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;
ll dp[nmax];
ll dd[nmax], xx[nmax];
ll sum[sqrt_n][sqrt_n];

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

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) {
			dd[i] = d;
			xx[i] = x;
		} else {
			ll l = i + d;
			ll r = i + d * (x + 1);
			if (l <= n) {
				events[l].emplace_back(0, d, i);
			}
			if (r <= n) {
				events[r].emplace_back(1, d, i);
			}
		}
	}
	for (ll d = 1; d <= sqrt_n_real; ++ d) {
		sort(events[d].begin(), events[d].end(), [] (const Event& lhs, const Event& rhs) {
			if (lhs.i != rhs.i) return lhs.i < rhs.i;
			if (lhs.d != rhs.d) return lhs.d < rhs.d;
			return lhs.type < rhs.type;
		});
	}
	dp[1] = 1;
	for (ll i = 2; i <= n; ++ i) {
		if (dd[i - 1] > 0) {
			ll d = dd[i - 1];
			ll x = xx[i - 1];
			for (ll j = 1; j <= x; ++ j) {
				ll ni = i + d * j;
				if (ni <= n) {
					add(dp[ni], dp[i - 1]);
				} else break;
			}
		}
		for (const auto& [type, d, j] : events[i]) {
			if (type == 0) {
				add(sum[d][j % d], dp[j]);
			} else {
				sub(sum[d][j % d], dp[j]);
			}
		}
		for (ll d = 1; d <= sqrt_n_real; ++ d) {
			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: 0 / 8
• Subtask 2: 0 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 0 / 29