Submission #994567

#	Time	Username	Problem	Language	Result	Execution time	Memory
994567		pavement	Trains (BOI24_trains)	C++17	100 / 100	1878 ms	789336 KiB

Main

#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) {
	//~ cout << "UPD " << pos << ' ' << v << '\n';
	for (; pos <= (int)ft.size(); pos += ls(pos)) {
		ft[pos - 1] = (ft[pos - 1] + v) % MOD;
	}
}

int ft_qry(vector<int> &ft, int pos) {
	//~ cout << "QU " << pos << '\n';
	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)) % 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';
}

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