oj.uz

Submission #994724

# Submission time Handle Problem Language Result Execution time Memory
994724 2024-06-08T04:32:43 Z WeIlIaN Trains (BOI24_trains) C++14
8 / 100
 7 ms 1372 KB 
#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define FOR(i, s, e) for(int i = s; i < e; i++)
#define REP(i, n) for(int i = 0; i < n; i++)
#define fir first
#define sec second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vll d(n), x(n);
	bool fl = true;
	REP(i, n) {
		cin>>d[i]>>x[i];
		if(d[i] != 1) {
			fl = false;
		}
	}
	if(n == 1) {
		cout<<1;
		return 0;
	}
	vll dp(n, 0);
	dp[0] = 1ll;
	if(fl) {
		ll sum = 1ll;
		priority_queue<pll, vpll, greater<pll>> pq;
		pq.push({x[0], 1ll});
		FOR(i, 1, n) {
			while(!pq.empty() && pq.top().fir < i) {
				sum = (sum - pq.top().sec) % MOD;
				pq.pop();
			}
			dp[i] = sum;
			sum = (sum * 2) % MOD;
			pq.push({x[i] + i, dp[i]});
		}
		ll ans = 0;
		REP(i, n) {
			ans = (ans + dp[i]) % MOD;
		}
		cout<<ans;
		return 0;
	}
	if(n <= 10000) {
		int nex;
		REP(i, n) {
			if(d[i] == 0) {
				continue;
			}
			FOR(j, 1, x[i]+1) {
				nex = i + d[i] * j;
				if(nex >= n) {
					break;
				}
				dp[nex] = (dp[nex] + dp[i]) % MOD;
			}
		}
		ll ans = 0;
		REP(i, n) {
			ans = (ans + dp[i]) % MOD;
		}
		cout<<ans;
		return 0;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 424 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 424 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 7 ms 604 KB Output is correct
21 Correct 0 ms 524 KB Output is correct
22 Correct 3 ms 604 KB Output is correct
23 Correct 2 ms 600 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 4 ms 668 KB Output is correct
26 Incorrect 1 ms 604 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 424 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 7 ms 604 KB Output is correct
21 Correct 0 ms 524 KB Output is correct
22 Correct 3 ms 604 KB Output is correct
23 Correct 2 ms 600 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 4 ms 668 KB Output is correct
26 Incorrect 1 ms 604 KB Output isn't correct
27 Halted 0 ms 0 KB -