Submission #1033571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033571		vjudge1	Trains (BOI24_trains)	C++98	37 / 100	826 ms	1048576 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
#define el cout << '\n';
using namespace std;

const int N = 1e5+5;
const int inf = 1e18;
const int LG = 31;
const int MOD = 1e9+7;
//const int mod = 998244353;

int n;
vector<int> g[N];
int dp[N],d[N],x[N];
int cnt=0;
int st[4*N],lazy[4*N];

void build(int id, int l, int r) {
    if (l == r) {
        st[id] = dp[l] % MOD;
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = (st[id * 2] + st[id * 2 + 1]) % MOD;
}

void push(int id, int l, int r) {
    if (lazy[id] != 0) {
        st[id] = (st[id] + lazy[id] * (r - l + 1)) % MOD;
        if (l != r) {
            lazy[id * 2] = (lazy[id * 2] + lazy[id]) % MOD;
            lazy[id * 2 + 1] = (lazy[id * 2 + 1] + lazy[id]) % MOD;
        }
        lazy[id] = 0;
    }
}

void update(int id, int l, int r, int u, int v, int val) {
    push(id, l, r);
    if (l > v || u > r) return;
    if (l >= u && r <= v) {
        lazy[id] = (lazy[id] + val) % MOD;
        push(id, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(id * 2, l, mid, u, v, val);
    update(id * 2 + 1, mid + 1, r, u, v, val);
    st[id] = (st[id * 2] + st[id * 2 + 1]) % MOD;
}

int get(int id, int l, int r, int u, int v) {
    push(id, l, r);
    if (l > v || u > r) return 0;
    if (l >= u && r <= v) {
        return st[id] % MOD;
    }
    int mid = (l + r) / 2;
    return (get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v)) % MOD;
}


void solve(){
    cin>>n;
    for(int i=1; i<=n; i++){
    	cin>>d[i]>>x[i];
    	if(d[i]==1) cnt++;
    	if(d==0) continue;
	}
	if(cnt==n){
	//	cout << "dm\n";
		fill(dp+1,dp+1+n,0);
		dp[1]=1;
		build(1,1,n);
		for(int i=1; i<n; i++){
			int v = get(1,1,n,i,i);
		//	cout << v << '\n';
			if(x[i]==0) continue;
			update(1,1,n,i+1,min(n,i+x[i]),v);
			for(int j=1; j<=n; j++){
			//	cout << get(1,1,n,j,j) << ' ';
			}
		//	el;
		}
		cout << get(1,1,n,1,n)%MOD;
		return;
	}
    for(int i=1; i<=n; i++){
    	if(d[i]==0) continue;
    	for(int j=i+d[i]; j<=min(i+d[i]*x[i],n); j+=d[i]){
    		g[i].pb(j);
		}
	}
	dp[1]=1;
	for(int i=1; i<n; i++){
		for(auto x:g[i]){
			dp[x] = (dp[x]+dp[i])%MOD;
		}
	}
	int ans=0;
	for(int i=1; i<=n; i++){
		ans+=dp[i];ans%=MOD;
	}
	cout << ans;
} 



signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
		el;
	}
}

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