Submission #1218992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218992		ani5h	Trains (BOI24_trains)	C++20	16 / 100	305 ms	250972 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using ll = long long;
 
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 

//const ll MOD = 998244353LL;
const ll MOD = 1e9 + 7;

template<const ll MOD> struct Modular {
    static const ll mod = MOD;
    ll v; explicit operator ll() const { return v; }
    Modular():v(0) {}
    Modular(ll _v) { v = ll((-MOD < _v && _v < MOD) ? _v : _v % MOD); if (v < 0) v += MOD; }
    friend Modular mpw(Modular a, ll p) {
        Modular ans = 1;
        for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans; }
    friend Modular inv(const Modular& a) { return mpw(a,MOD-2);}
    friend bool operator!=(const Modular& a, const Modular& b) { return !(a == b); }
    friend bool operator<(const Modular& a, const Modular& b) { return a.v < b.v; }
    Modular& operator+=(const Modular& o) { if ((v += o.v) >= MOD) v -= MOD; return *this; }
    Modular& operator-=(const Modular& o) { if ((v -= o.v) < 0) v += MOD; return *this; }
    Modular& operator*=(const Modular& o) { v = ll((ll)v*o.v%MOD); return *this; }
    Modular& operator/=(const Modular& o) { return (*this) *= inv(o); }
    Modular operator-() const { return Modular(-v); }
    Modular& operator++() { return *this += 1; }
    Modular& operator--() { return *this -= 1; }
    friend Modular operator+(Modular a, const Modular& b) { return a += b; }
    friend Modular operator-(Modular a, const Modular& b) { return a -= b; }
    friend Modular operator*(Modular a, const Modular& b) { return a *= b; }
    friend Modular operator/(Modular a, const Modular& b) { return a /= b; }
    friend istream& operator>>(istream& inp, Modular& a) { ll x; inp >> x; a = Modular(x); return inp;}
    friend ostream& operator<<(ostream& out, const Modular& a) { out << a.v; return out; }
};

using Mint = Modular<MOD>;
void solve() {
    int n;
    cin >> n;

    vector<int> s(n), l(n);
    for(int i = 0; i < n; i++)
        cin >> s[i] >> l[i];

    int bs = max((int)sqrt(n), 1);

    vector<Mint> dp(n + 1, Mint(0));
    vector<vector<Mint>> pref(bs, vector<Mint>(n + 1, Mint(0)));

    dp[1] = Mint(1);

    for(int i = 1; i <= n; i++) {
        Mint cur = dp[i];

        for(int j = 1; j < bs; j++) {
            if(i - j > 0)
                pref[j][i] += pref[j][i - j];

            cur += pref[j][i];
        }

        dp[i] = cur;

        int hop = s[i - 1], bound = l[i - 1];
        ll lo = i + hop, hi = min(n, i + hop * bound);

        if(lo > n)
            continue;

        if(hop < bs) {
            pref[hop][lo] += dp[i];
            
            if(hi + hop <= n)
                pref[hop][hi + hop] -= dp[i];
        } else {
            for(int j = lo; j <= hi; j += hop)
                dp[j] += dp[i];
        }
    }

    Mint ans = 0;
    for(auto &x : dp)
        ans += x;

    cout << ans << '\n';
}

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

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