Submission #1033640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033640		fimh	Trains (BOI24_trains)	C++17	100 / 100	295 ms	253276 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define fi first
#define pll pair<long long, long long>
#define se second
#define isz(a) (int)a.size()
using namespace std;

const long long inf = 1e18;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int block = 320;

int n; 
int d[maxn], x[maxn], dp[maxn], ps[maxn][block];
// dp[i]: so subsequence bat dau tu i
// dp[i] = 1 + dp[j], j = i + t * d (t <= x[i])

void sub2(){
    dp[n] = 1;
    for (int i = n - 1; i >= 1; --i){
        dp[i] = 1;
        if (d[i] == 0) continue;
        int j = i + d[i], cnt = 1;
        while (j <= n && cnt <= x[i]){
            dp[i] += dp[j]; dp[i] %= mod;
            j += d[i]; ++cnt;
        }
    }
    cout << dp[1];
}

void subfull(){
    dp[n] = 1;
    for (int i = 1; i <= block; ++i) ps[n][i] = 1;
    for (int i = n - 1; i >= 1; --i){
        dp[i] = 1;
        if ((d[i] >= block || x[i] <= block) && d[i]){ // loop sqrt()
            int j = i + d[i], cnt = 1;
            while (j <= n && cnt <= x[i]){
                dp[i] += dp[j]; dp[i] %= mod;
                j += d[i]; ++cnt;
            }
        }else if (d[i]) { // d[i] < block
            int r = (i + d[i] <= n ? ps[i + d[i]][d[i]] : 0);
            int l = (i + (x[i] + 1) * d[i] <= n ? ps[i + (x[i] + 1) * d[i]][d[i]] : 0);
            dp[i] += (r - l + mod) % mod; dp[i] %= mod;
        }
        for (int j = 1; j <= block; ++j){
            ps[i][j] = (i + j <= n ? ps[i + j][j] : 0) + dp[i];
            ps[i][j] %= mod;
        }
    }
    cout << dp[1];
}

void solve(){
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> d[i] >> x[i];
    if (n <= 10000) sub2();
    else subfull();
}   

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1; // cin >> t;
    while (t--){
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'void subfull()':
Main.cpp:35:47: warning: iteration 319 invokes undefined behavior [-Waggressive-loop-optimizations]
   35 |     for (int i = 1; i <= block; ++i) ps[n][i] = 1;
      |                                      ~~~~~~~~~^~~
Main.cpp:35:23: note: within this loop
   35 |     for (int i = 1; i <= block; ++i) ps[n][i] = 1;
      |                     ~~^~~~~~~~
Main.cpp:50:22: warning: iteration 319 invokes undefined behavior [-Waggressive-loop-optimizations]
   50 |             ps[i][j] = (i + j <= n ? ps[i + j][j] : 0) + dp[i];
      |             ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:49:27: note: within this loop
   49 |         for (int j = 1; j <= block; ++j){
      |                         ~~^~~~~~~~

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