oj.uz

Submission #994601

# Submission time Handle Problem Language Result Execution time Memory
994601 2024-06-08T02:15:33 Z WeIlIaN Trains (BOI24_trains) C++14
0 / 100
 614 ms 1876 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 = 1;
		priority_queue<pll, vpll, greater<pll>> pq;
		pq.push({x[0], 0ll});
		FOR(i, 1, n) {
			while(!pq.empty() && pq.top().fir < i) {
				sum = (sum - dp[pq.top().sec]) % MOD;
				pq.pop();
			}
			dp[i] = sum;
			sum = (sum * 2) % MOD;
			pq.push({x[i] + i, i});
		}
		ll ans = 0;
		REP(i, n) {
			ans += dp[i];
		}
		cout<<ans;
		return 0;
	}
	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;
			//cout<<i+1<<' '<<nex+1<<' '<<dp[nex]<<' '<<dp[i]<<endl;
		}
	}
	ll ans = 0;
	REP(i, n) {
		ans += dp[i];
		cout<<dp[i]<<' ';
	}
	cout<<ans;
	return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 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 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

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

Subtask #5
0 / 29.0

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