Submission #994603

#	Time	Username	Problem	Language	Result	Execution time	Memory
994603		WeIlIaN	Trains (BOI24_trains)	C++14	21 / 100	92 ms	2140 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;
	}
	vll dp(n, 0);
	dp[0] = 1ll;
	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;
				//cout<<i+1<<' '<<nex+1<<' '<<dp[nex]<<' '<<dp[i]<<endl;
			}
		}
		ll ans = 0;
		REP(i, n) {
			ans = (ans + dp[i]) % MOD;
		}
		cout<<ans;
		return 0;
	}
	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 = (ans + dp[i]) % MOD;
		}
		cout<<ans;
		return 0;
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 34
• Subtask 5: 0 / 29