Submission #1073688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073688		Dan4Life	Trains (BOI24_trains)	C++17	100 / 100	201 ms	6480 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using ar2 = array<int,2>;
const int mxN = (int)1e5+10;
const int MOD = (int)1e9+7;
const int B = (int)330;
int n, ans;
int x[mxN], d[mxN];
int dp[mxN], pref[mxN];
int seg[mxN*2+10];
int tot[B][B];

int32_t main(){
	cin >> n; dp[0] = 1;
	for(int i = 0; i < n; i++)
		cin >> d[i] >> x[i];
	set<ar2> rem;
	for(int i = 0; i < n; i++){
		for(int j = 1; j < B; j++)
			dp[i]+=tot[i%j][j], dp[i]%=MOD;
		if(d[i]>=B){
			for(int j = 1; j<=x[i] and d[i]; j++){
				if(i+j*d[i]>=n) break; 
				dp[i+j*d[i]]+=dp[i];
				dp[i+j*d[i]]%=MOD;
			}
		}
		else if(d[i]){
			int nx = i+x[i]*d[i];
			if(nx<=n) rem.insert({nx, i});
			tot[i%d[i]][d[i]]+=dp[i];
			tot[i%d[i]][d[i]]%=MOD;
		}
		while(sz(rem)){
			auto [j,I] = *begin(rem);
			if(j>i) break;
			int l = I%d[I], l2 = d[I];
			tot[l][l2]-=dp[I];
			tot[l][l2]+=MOD;
			tot[l][l2]%=MOD;
			rem.erase(begin(rem));
		}
		ans+=dp[i]; ans%=MOD;
	}
	cout << ans << "\n";
}

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