Submission #994588

#	Time	Username	Problem	Language	Result	Execution time	Memory
994588		WeIlIaN	Trains (BOI24_trains)	C++14	0 / 100	5 ms	1116 KiB

Main

#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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 34
• Subtask 5: 0 / 29