Submission #1033309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033309		borisAngelov	Trains (BOI24_trains)	C++17	34 / 100	93 ms	5844 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const int BLOCK_SIZE = 355;
const int mod = 1e9 + 7;

int n;
int d[maxn], x[maxn];
int dp[maxn];
int pref[maxn];

int prefSmall[BLOCK_SIZE][BLOCK_SIZE];
vector<tuple<int, int, int>> toRemove[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> d[i] >> x[i];
        x[i] = min(x[i], (n - i) / d[i] + ((n - i) % d[i] != 0));
    }

    int big = sqrt(n);
    int ans = 0;

    for (int i = 1; i <= n; ++i)
    {
        for (auto [small, rem, value] : toRemove[i])
        {
            prefSmall[small][rem] -= value;
            if (prefSmall[small][rem] < 0) prefSmall[small][rem] += mod;
        }

        if (i == 1)
        {
            dp[i] = 1;
        }
        else
        {
            for (int small = 1; small < big; ++small)
            {
                dp[i] += prefSmall[small][i % small];
                if (dp[i] >= mod) dp[i] -= mod;
            }
        }

        if (d[i] >= big)
        {
            for (int j = i + d[i]; j <= n; j += d[i])
            {
                dp[j] += dp[i];
                if (dp[j] >= mod) dp[j] -= mod;
            }
        }
        else if (d[i] != 0)
        {
            prefSmall[d[i]][i % d[i]] += dp[i];
            if (prefSmall[d[i]][i % d[i]] >= mod) prefSmall[d[i]][i % d[i]] -= mod;
            toRemove[min(i + x[i] * d[i] + 1, n + 1)].push_back({d[i], i % d[i], dp[i]});
        }

        ans += dp[i];
        if (ans >= mod) ans -= mod;

        //cout << i << " :: " << dp[i] << endl;
    }

    cout << ans << endl;

    return 0;
}

/*
5
1 3
1 1
0 4
1 2
1 2

5
1 3
1 1
1 2
1 2
1 2
2 :: 1
3 :: 2
4 :: 3
5 :: 5

12
3 1000000000
5 1000000000
2 1000000000
7 1000000000
4 1000000000
1 1000000000
1 1000000000
5 1000000000
2 1000000000
1 1000000000
1 1000000000
3 1000000000
here 2 :: 0
here 3 :: 0
here 4 :: 1
here 5 :: 0
here 6 :: 0
here 7 :: 1
here 8 :: 1
here 9 :: 1
here 10 :: 2
here 11 :: 5
here 12 :: 8
*/

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