Submission #1084831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084831		kilkuwu	Trains (BOI24_trains)	C++17	100 / 100	350 ms	132220 KiB

Main

#include <bits/stdc++.h>

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

#define nl '\n'

template <int md>
struct Modular {
    int v;
    constexpr Modular() : v(0) {}
    template <typename T>
    static inline int normalize(const T& x) {
        int res = -mod() <= x && x < mod() ? static_cast<int>(x) : static_cast<int>(x % mod());
        return res + (res < 0) * mod();
    }
    static constexpr int mod() {
        return md;
    }
    template <typename U>
    Modular(const U& x) : v(normalize(x)) {}
    const int& operator()() const {
        return v;
    }
    template <typename U>
    explicit operator U() const {
        return static_cast<U>(v);
    }
    using M = Modular;
    template <typename U>
    friend std::enable_if_t<std::is_integral_v<U>, M> power(M b, U e) {
        assert(e >= 0);
        M ans = 1;
        while (e) {
            if (e & 1) ans *= b;
            b *= b;
            e >>= 1;
        }
        return ans;
    }
    M inv() const {
        M res = power(*this, mod() - 2);
        return res;
    }
    M& operator+=(const M& y) {
        return v += y.v, v -= (v >= mod()) * mod(), *this;
    }
    M& operator-=(const M& y) {
        return v -= y.v, v += (v < 0) * mod(), *this;
    }
    M& operator*=(const M& y) {
        return v = (int)((int64_t)v * y.v % mod()), *this;
    }
    M& operator/=(const M& y) {
        return *this *= y.inv();
    }
    M& operator++() {
        return v++, v = (v == mod()) ? 0 : v, *this;
    }
    M& operator--() {
        return v = (v == 0) ? mod() : v, v--, *this;
    }
    M operator++(int) {
        M res(*this);
        return ++(*this), res;
    }
    M operator--(int) {
        M res(*this);
        return --(*this), res;
    }
    M operator+() const {
        return M(v);
    }
    M operator-() const {
        return M(-v);
    }
    friend bool operator==(const M& x, const M& y) {
        return x.v == y.v;
    }
    friend bool operator<(const M& x, const M& y) {
        return x.v < y.v;
    }
    friend bool operator>(const M& x, const M& y) {
        return x.v > y.v;
    }
    friend bool operator<=(const M& x, const M& y) {
        return x.v <= y.v;
    }
    friend bool operator>=(const M& x, const M& y) {
        return x.v >= y.v;
    }
    friend bool operator!=(const M& x, const M& y) {
        return x.v != y.v;
    }
    template <typename Istream>
    friend Istream& operator>>(Istream& is, M& y) {
        int64_t x;
        is >> x;
        y.v = y.normalize(x);
        return is;
    }
    template <typename Ostream>
    friend Ostream& operator<<(Ostream& os, const M& y) {
        return os << y.v;
    }
    friend M operator+(const M& x, const M& y) {
        return M(x) += y;
    }
    friend M operator-(const M& x, const M& y) {
        return M(x) -= y;
    }
    friend M operator*(const M& x, const M& y) {
        return M(x) *= y;
    }
    friend M operator/(const M& x, const M& y) {
        return M(x) /= y;
    }
};

constexpr int md = 1e9 + 7;
using Mint = Modular<md>;


signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    std::vector<int> d(N), x(N);
    for (int i = 0; i < N; i++) {
        std::cin >> d[i] >> x[i];
    }

    std::vector<std::pair<int, int>> compressed;

    for (int i = 0; i < N; i++) {
        if (d[i] != 0) {
            compressed.emplace_back(i % d[i], d[i]);
        }
    }

    std::sort(compressed.begin(), compressed.end());
    compressed.erase(std::unique(compressed.begin(), compressed.end()), compressed.end());

    auto get_id = [&](std::pair<int, int> key) -> int {
        return std::lower_bound(compressed.begin(), compressed.end(), key) - compressed.begin();
    };

    int sz = compressed.size();


    std::vector<int> belong(N, -1);

    for (int i = 0; i < N; i++) {
        if (d[i] != 0) {
            belong[i] = get_id({i % d[i], d[i]});
        }
    }


    int B = std::sqrt(N);
    //dbg(B);
    int num_block = (N - 1) / B + 1;
    std::vector<std::vector<Mint>> add(sz, std::vector<Mint>(num_block));

    std::vector<int> has_update(num_block, 0);

    std::vector<Mint> dp(N);

    auto collapse_block = [&](int b) -> void { // O(N)

        if (!has_update[b]) return;
        has_update[b] = 0;
        int lb = b * B;
        int rb = std::min((b + 1) * B, N);
        for (int i = 0; i < sz; i++) {
            // moi thang nay co 1 delta
            auto [from, delta] = compressed[i];
            // from + x * delta >= lb
            if (from < lb) {
                int t = (lb - from + delta - 1) / delta;
                from += t * delta;
            }
            if (from >= rb) continue;

            for (int j = from; j < rb; j += delta) {
                dp[j] += add[i][b];
            }
        }
    };

    // 1,  x[i] = 3
    // 1 + 1 * 1 -> 1 + 3 * 1
    // 2 -> 4

    auto update = [&](int index) -> void {
        int id = belong[index];
        auto val = dp[index];
        int l = index + d[index];
        int max_t = (N - 1 - index) / d[index];
        int r = index + std::min(max_t, x[index]) * d[index];
        if (l > r) return;
        int bl = l / B;
        int br = r / B;



        if (bl == br) {
            for (int i = l; i <= r; i += d[index]) {

                dp[i] += val;
            }
            return;
        }
        for (int i = l; i < B * (bl + 1); i += d[index]) {
            dp[i] += val;
        }

        for (int b = bl + 1; b < br; b++) {
            has_update[b] = 1;
            add[id][b] += val;
        }

        for (int i = r; i >= br * B; i -= d[index]) {
            dp[i] += val;
        }
    };


   // dbg("got here");
    dp[0] = 1;
    Mint res = 0;
//
// bought already we can go there if bought lmao
//
    for (int i = 0; i < N; i++) {
        collapse_block(i / B);
        res += dp[i];
       // dbg(i, dp[i]);
        if (d[i] == 0) continue;
        update(i);
    }

    std::cout << res << nl;


}

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