Submission #1039903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039903		ttttttttttttth	Trains (BOI24_trains)	C++17	100 / 100	167 ms	255944 KiB

Main

// Author: Ivan Teo
// Created: Wed Jul 31 18:10:56 2024

#define TASKNAME "BOITRAINS"
#include <bits/stdc++.h>
using namespace std;

#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define ell cerr << "\n=========================================\n"
#define el cerr << '\n'
#define Unique(v) v.erase(unique(alll(v)), v.end())
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
    assert(l <= r);
    return uniform_int_distribution<int> (l, r)(rng);
}
template<int D, typename T> struct Vec : public vector < Vec < D - 1, T >>
{
    template<typename... Args> Vec(int n = 0, Args... args) : vector < Vec < D - 1, T >> (n, Vec < D - 1, T > (args...)) {}
};
template<typename T> struct Vec<1, T> : public vector<T>
{
    Vec(int n = 0, const T &val = T()) : vector<T>(n, val) {}
};

const int N = 1e5 + 5;
const int BLOCK = sqrt(N);
const int MOD = 1e9 + 7;

int add(int a, int b)
{
    a += b;
    if (a < 0) a += MOD;
    if (a >= MOD) a -= MOD;
    return a;
}

int f[N], rem[N][BLOCK], n, d[N], x[N];
vector<ii> ev[N];

void ivan()
{
    cin >> n;
    fore(i, 1, n) cin >> d[i] >> x[i];
    f[1] = 1;
    fore(i, 1, n)
    {
        if (d[i] < BLOCK)
            rem[i][d[i]] = add(rem[i][d[i]], f[i]),
                           ev[min(N - 1, i + d[i] * x[i])].pb(d[i], f[i]);
        for (auto [d, x] : ev[i]) rem[i][d] = add(rem[i][d], -x);
        fore(j, 1, BLOCK)
        if (i + j <= n)
            rem[i + j][j] = add(rem[i][j], rem[i + j][j]),
                            f[i + j] = add(f[i + j], rem[i][j]);
        if (d[i] >= BLOCK)
        {
            fore(cnt, 1, x[i])
            {
                if (i + cnt * d[i] <= n)
                {
                    int j = i + cnt * d[i];
                    f[j] = add(f[j], f[i]);
                }
                else break;
            }
        }
    }
    int ans = 0;
    fore(i, 1, n) ans = add(ans, f[i]);
    cout << ans;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    if (fopen(TASKNAME".inp", "r"))
    {
        freopen(TASKNAME".inp", "r", stdin);
        freopen(TASKNAME".out", "w", stdout);
    }
    int tc = 1;
    // cin >> tc;
    while (tc--) ivan();
    el, cerr << "Execution Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s", el;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(TASKNAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(TASKNAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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