oj.uz

답안 #994566

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
994566 2024-06-08T01:27:55 Z pavement Trains (BOI24_trains) C++17
8 / 100
 891 ms 381100 KB 
#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) {
	for (; pos <= (int)ft.size(); pos += ls(pos)) {
		ft[pos - 1] = (ft[pos - 1] + v) % MOD;
	}
}

int ft_qry(vector<int> &ft, int pos) {
	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 + 1)) % 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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3176 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3160 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct
11 Correct 1 ms 3164 KB Output is correct
12 Correct 2 ms 3164 KB Output is correct
13 Correct 1 ms 3164 KB Output is correct
14 Correct 1 ms 3164 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 1 ms 3164 KB Output is correct
17 Correct 1 ms 3164 KB Output is correct
18 Correct 1 ms 3164 KB Output is correct
19 Correct 1 ms 3164 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3176 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3160 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct
11 Correct 1 ms 3164 KB Output is correct
12 Correct 2 ms 3164 KB Output is correct
13 Correct 1 ms 3164 KB Output is correct
14 Correct 1 ms 3164 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 1 ms 3164 KB Output is correct
17 Correct 1 ms 3164 KB Output is correct
18 Correct 1 ms 3164 KB Output is correct
19 Correct 1 ms 3164 KB Output is correct
20 Incorrect 94 ms 68156 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Incorrect 67 ms 53756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 891 ms 381100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3176 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3160 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct
11 Correct 1 ms 3164 KB Output is correct
12 Correct 2 ms 3164 KB Output is correct
13 Correct 1 ms 3164 KB Output is correct
14 Correct 1 ms 3164 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 1 ms 3164 KB Output is correct
17 Correct 1 ms 3164 KB Output is correct
18 Correct 1 ms 3164 KB Output is correct
19 Correct 1 ms 3164 KB Output is correct
20 Incorrect 94 ms 68156 KB Output isn't correct
21 Halted 0 ms 0 KB -