oj.uz

Submission #994588

# Submission time Handle Problem Language Result Execution time Memory
994588 2024-06-08T01:59:39 Z WeIlIaN Trains (BOI24_trains) C++14
0 / 100
 5 ms 1116 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;
	}
	if(fl) {
		ll sum = 1;
		vll dp(n);
		priority_queue<pll, vpll, greater<pll>> pq;
		dp[0] = 1ll;
		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();
			}
			if(sum == 0) {
				cout<<0;
				return 0;
			}
			dp[i] = sum;
			sum = (sum * 2) % MOD;
			pq.push({x[i] + i, i});
		}
		cout<<dp[n-1];
	}
}

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 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1116 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 -