Submission #1063040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063040		quanmcvn	Trains (BOI24_trains)	C++14	71 / 100	2082 ms	226240 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, 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) {
			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].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) {
		for (const auto& j : from[i]) {
			add(dp[i], dp[j]);
		}
		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;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:72:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |   for (const auto& [type, d, j] : events[i]) {
      |                    ^

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