Submission #1033747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033747		Tozzyyyy	Trains (BOI24_trains)	C++14	100 / 100	158 ms	7116 KiB

Main

#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define pii pair<int , int>
#define fi first
#define se second
#define bit(i,j) ((j >> i) & 1)
using namespace std;
 
const long long inf = 1e18;
const int mod = 1e9+7;
const int MAXN = 2e5+100;
 
#define int long long
 
int mp[500][500];
int32_t main(){
  	//freopen("B.inp", "r", stdin);
	//freopen("B.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<int> d(n+1) , x(n+1);
	const int block = 320;
 
	for(int i = 1 ; i <= n ; i++) cin >> d[i] >> x[i];
 
	vector<int> dp(n+1);
	dp[1] = 1;
	priority_queue<pll , vector<pll> , greater<pll>> Q;
	if(d[1] > block){
		for(int i = 1 + d[1] ; i <= min(n , 1 + x[1] * d[1]) ; i += d[1]) dp[i] += 1;
	}else if(d[1] != 0){
		Q.push({1 + x[1] * d[1] , 1});
		mp[d[1]][1%d[1]] += 1;
	}
	int ans = 1;
	for(int i = 2 ; i <= n ; i++){
		while(Q.size()){
			pll t = Q.top();
			if(t.fi < i){
				if(d[t.se] != 0){
					mp[d[t.se]][t.se%d[t.se]] = (mp[d[t.se]][t.se%d[t.se]] - dp[t.se] + mod) % mod;
				}
				Q.pop();
			}
			else break;
		}
		for(int j = 1 ; j <= block ; j++) dp[i] = (dp[i] + mp[j][i%j]) % mod;
		ans = (ans + dp[i]) % mod;
			
		if(d[i] == 0) continue;
		if(d[i] > block){
			for(int j = i + d[i] ; j <= min(n , i + x[i] * d[i]) ; j += d[i]) dp[j] = (dp[j] + dp[i]) % mod;
		}else{
			Q.push({i + x[i] * d[i] , i});
			mp[d[i]][i%d[i]] += dp[i];
			mp[d[i]][i%d[i]] %= mod;
		}
	}
	cout << ans << "\n";
	return 0;
}

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