Submission #9009219


Source Code Expand

Copy
#line 1 "a.cpp"
#include <bits/stdc++.h>
#line 2 "/home/ubuntu/Library/data_structure/segment_tree.hpp"
#include <algorithm>
#include <cassert>
#include <vector>
#line 1 "/home/ubuntu/Library/utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
#line 6 "/home/ubuntu/Library/data_structure/segment_tree.hpp"

/**
 * @brief a segment tree / セグメント木
 * @tparam Monoid (commutativity is not required)
 */
template <class Monoid>
struct segment_tree {
    typedef typename Monoid::value_type value_type;
    const Monoid mon;
    int n;
    std::vector<value_type> a;
    segment_tree() = default;
    segment_tree(int n_, const Monoid & mon_ = Monoid()) : mon(mon_) {
        n = 1; while (n < n_) n *= 2;
        a.resize(2 * n - 1, mon.unit());
    }
    void point_set(int i, value_type b) {  // 0-based
        assert (0 <= i and i < n);
        a[i + n - 1] = b;
        for (i = (i + n) / 2; i > 0; i /= 2) {  // 1-based
            a[i - 1] = mon.mult(a[2 * i - 1], a[2 * i]);
        }
    }
    value_type range_concat(int l, int r) {  // 0-based, [l, r)
        assert (0 <= l and l <= r and r <= n);
        value_type lacc = mon.unit(), racc = mon.unit();
        for (l += n, r += n; l < r; l /= 2, r /= 2) {  // 1-based loop, 2x faster than recursion
            if (l % 2 == 1) lacc = mon.mult(lacc, a[(l ++) - 1]);
            if (r % 2 == 1) racc = mon.mult(a[(-- r) - 1], racc);
        }
        return mon.mult(lacc, racc);
    }

    /**
     * @brief a fast & semigroup-friendly version constructor
     * @note $O(n)$
     */
    segment_tree(const std::vector<value_type> & a_, const Monoid & mon_ = Monoid()) : mon(mon_) {
        n = 1; while (n < a_.size()) n *= 2;
        a.resize(2 * n - 1, mon.unit());
        std::copy(ALL(a_), a.begin() + (n - 1));
        unsafe_rebuild();
    }
    /**
     * @brief update a leaf node without updating ancestors
     * @note $O(1)$
     */
    void unsafe_point_set(int i, value_type b) {  // 0-based
        assert (0 <= i and i < n);
        a[i + n - 1] = b;
    }
    /**
     * @brief re-build non-leaf nodes from leaf nodes
     * @note $O(n)$
     */
    void unsafe_rebuild() {
        REP_R (i, n - 1) {
            a[i] = mon.mult(a[2 * i + 1], a[2 * i + 2]);
        }
    }
};
#line 2 "/home/ubuntu/Library/number/matrix_template.hpp"
#include <array>
#include <cstdint>
#line 1 "/home/ubuntu/Library/utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
#line 5 "/home/ubuntu/Library/number/matrix_template.hpp"

template <typename T, size_t H, size_t W>
using matrix = std::array<std::array<T, W>, H>;

template <typename T, size_t A, size_t B, size_t C>
matrix<T, A, C> operator * (matrix<T, A, B> const & a, matrix<T, B, C> const & b) {
    matrix<T, A, C> c = {};
    REP (y, A) REP (z, B) REP (x, C) c[y][x] += a[y][z] * b[z][x];
    return c;
}
template <typename T, size_t H, size_t W>
std::array<T, H> operator * (matrix<T, H, W> const & a, std::array<T, W> const & b) {
    std::array<T, H> c = {};
    REP (y, H) REP (z, W) c[y] += a[y][z] * b[z];
    return c;
}

template <typename T, size_t H, size_t W>
matrix<T, H, W> operator + (matrix<T, H, W> const & a, matrix<T, H, W> const & b) {
    matrix<T, H, W> c;
    REP (y, H) REP (x, W) c[y][x] = a[y][x] + b[y][x];
    return c;
}

template <typename T, size_t N>
std::array<T, N> operator + (std::array<T, N> const & a, std::array<T, N> const & b) {
    std::array<T, N> c;
    REP (i, N) c[i] = a[i] + b[i];
    return c;
}

template <typename T, size_t H, size_t W>
matrix<T, H, W> zero_matrix() {
    return {};
}

template <typename T, size_t N>
matrix<T, N, N> unit_matrix() {
    matrix<T, N, N> a = {};
    REP (i, N) a[i][i] = 1;
    return a;
}

template <typename T, size_t N>
matrix<T, N, N> powmat(matrix<T, N, N> x, int64_t k) {
    matrix<T, N, N> y = unit_matrix<T, N>();
    for (; k; k >>= 1) {
        if (k & 1) y = y * x;
        x = x * x;
    }
    return y;
}
#line 2 "/home/ubuntu/Library/monoids/dual.hpp"

/**
 * @see http://hackage.haskell.org/package/base/docs/Data-Monoid.html#t:Dual
 */
template <class Monoid>
struct dual_monoid {
    typedef typename Monoid::value_type value_type;
    Monoid base;
    value_type unit() const { return base.unit(); }
    value_type mult(const value_type & a, const value_type & b) const { return base.mult(b, a); }
};
#line 3 "/home/ubuntu/Library/monoids/matrix_template.hpp"

template <class T, int N>
struct matrix_monoid {
    typedef matrix<T, N, N> value_type;
    value_type f;
    value_type unit() const {
        return unit_matrix<T, N>();
    }
    value_type mult(const value_type & f, const value_type & g) const {
        return f * g;
    }
};
#line 2 "/home/ubuntu/Library/modulus/mint.hpp"
#include <algorithm>
#include <cassert>
#include <iostream>

inline constexpr int32_t modpow(uint_fast64_t x, uint64_t k, int32_t MOD) {
    assert (0 <= x and x < MOD);
    uint_fast64_t y = 1;
    for (; k; k >>= 1) {
        if (k & 1) (y *= x) %= MOD;
        (x *= x) %= MOD;
    }
    assert (0 <= y and y < MOD);
    return y;
}
inline int32_t modinv(int32_t value, int32_t MOD) {
    assert (0 <= value and value < MOD);
    assert (value != 0);
    int64_t a = value, b = MOD;
    int64_t x = 0, y = 1;
    for (int64_t u = 1, v = 0; a; ) {
        int64_t q = b / a;
        x -= q * u; std::swap(x, u);
        y -= q * v; std::swap(y, v);
        b -= q * a; std::swap(b, a);
    }
    assert (value * x + MOD * y == b and b == 1);
    if (x < 0) x += MOD;
    assert (0 <= x and x < MOD);
    return x;
}

template <int32_t MOD>
struct mint {
    int32_t value;
    mint() : value() {}
    mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {}
    mint(int32_t value_, std::nullptr_t) : value(value_) {}
    explicit operator bool() const { return value; }
    inline constexpr mint<MOD> operator + (mint<MOD> other) const { return mint<MOD>(*this) += other; }
    inline constexpr mint<MOD> operator - (mint<MOD> other) const { return mint<MOD>(*this) -= other; }
    inline constexpr mint<MOD> operator * (mint<MOD> other) const { return mint<MOD>(*this) *= other; }
    inline constexpr mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline constexpr mint<MOD> & operator -= (mint<MOD> other) { this->value -= other.value; if (this->value <    0) this->value += MOD; return *this; }
    inline constexpr mint<MOD> & operator *= (mint<MOD> other) { this->value = (uint_fast64_t)this->value * other.value % MOD; return *this; }
    inline constexpr mint<MOD> operator - () const { return mint<MOD>(this->value ? MOD - this->value : 0, nullptr); }
    inline constexpr mint<MOD> pow(uint64_t k) const { return mint<MOD>(modpow(value, k, MOD), nullptr); }
    inline mint<MOD> inv() const { return mint<MOD>(modinv(value, MOD), nullptr); }
    inline constexpr mint<MOD> operator /  (mint<MOD> other) const { return *this *  other.inv(); }
    inline constexpr mint<MOD> operator /= (mint<MOD> other)       { return *this *= other.inv(); }
    inline constexpr bool operator == (mint<MOD> other) const { return value == other.value; }
    inline constexpr bool operator != (mint<MOD> other) const { return value != other.value; }
};
template <int32_t MOD> mint<MOD> operator * (int64_t value, mint<MOD> n) { return mint<MOD>(value) * n; }
template <int32_t MOD> std::istream & operator >> (std::istream & in, mint<MOD> & n) { int64_t value; in >> value; n = value; return in; }
template <int32_t MOD> std::ostream & operator << (std::ostream & out, mint<MOD> n) { return out << n.value; }
#line 1 "/home/ubuntu/Library/utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
#line 8 "a.cpp"
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr int K = 10;

int main() {
    // input the sequence
    int n; cin >> n;
    vector<int> h(n);
    REP (i, n) {
        cin >> h[i];
    }

    // input queries
    int d; cin >> d;
    vector<int> s(d);
    vector<int> t(d);
    REP (i, d) {
        cin >> s[i] >> t[i];
        -- s[i];
        -- t[i];
    }

    // compute the left-half of the segment tree to avoid MLE
    int middle = n / 2;
    segment_tree<dual_monoid<matrix_monoid<mint<MOD>, K> > > segtree(middle + 3);
    REP (i, middle) {
        matrix<mint<MOD>, K, K> f = {};
        REP (j, h[i]) {
            f[j][0] = 1;
        }
        REP (j, K - 1) {
            f[j][j + 1] = 1;
        }
        segtree.unsafe_point_set(i, f);
    }
    segtree.unsafe_rebuild();
    vector<array<mint<MOD>, K> > left(d);
    vector<mint<MOD> > answer(d);
    array<mint<MOD>, K> x = {{ 1 }};
    REP (i, d) {
        if (t[i] < middle) {
            auto f = segtree.range_concat(s[i], t[i]);
            answer[i] = (f * x)[0];
        } else if (s[i] < middle and middle <= t[i]) {
            auto f = segtree.range_concat(s[i], middle);
            left[i] = f * x;
        }
    }

    // compute the right-half of the segment tree
    REP3 (i, middle, n) {
        matrix<mint<MOD>, K, K> f = {};
        REP (j, h[i]) {
            f[j][0] = 1;
        }
        REP (j, K - 1) {
            f[j][j + 1] = 1;
        }
        segtree.unsafe_point_set(i - middle, f);
    }
    segtree.unsafe_rebuild();
    REP (i, d) {
        if (middle <= s[i]) {
            auto f = segtree.range_concat(s[i] - middle, t[i] - middle);
            answer[i] = (f * x)[0];
        } else if (s[i] < middle and middle <= t[i]) {
            auto right = segtree.range_concat(0, t[i] - middle);
            answer[i] = (right * left[i])[0];
        }
    }

    // output answers
    REP (i, d) {
        cout << answer[i] << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task D - ぴょんぴょんトレーニング
User kimiyuki
Language C++14 (GCC 5.4.1)
Score 100
Code Size 10517 Byte
Status
Exec Time 1468 ms
Memory 206592 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0-sample01.txt, subtask0-sample02.txt
Subtask1 30 / 30 subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt
Subtask2 70 / 70 subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt
Case Name Status Exec Time Memory
subtask0-sample01.txt 1 ms 256 KB
subtask0-sample02.txt 1 ms 256 KB
subtask1-01.txt 1 ms 256 KB
subtask1-02.txt 2 ms 256 KB
subtask1-03.txt 4 ms 256 KB
subtask1-04.txt 9 ms 384 KB
subtask1-05.txt 14 ms 384 KB
subtask1-06.txt 45 ms 512 KB
subtask1-07.txt 77 ms 640 KB
subtask1-08.txt 102 ms 640 KB
subtask1-09.txt 126 ms 768 KB
subtask1-10.txt 130 ms 768 KB
subtask1-11.txt 130 ms 768 KB
subtask1-12.txt 124 ms 768 KB
subtask1-13.txt 122 ms 768 KB
subtask1-14.txt 128 ms 768 KB
subtask1-15.txt 129 ms 768 KB
subtask1-16.txt 123 ms 768 KB
subtask2-01.txt 158 ms 13184 KB
subtask2-02.txt 157 ms 13184 KB
subtask2-03.txt 240 ms 26112 KB
subtask2-04.txt 447 ms 51968 KB
subtask2-05.txt 458 ms 51968 KB
subtask2-06.txt 816 ms 103424 KB
subtask2-07.txt 880 ms 103680 KB
subtask2-08.txt 1447 ms 206464 KB
subtask2-09.txt 1466 ms 206464 KB
subtask2-10.txt 1463 ms 206464 KB
subtask2-11.txt 1468 ms 206464 KB
subtask2-12.txt 1461 ms 206464 KB
subtask2-13.txt 1466 ms 206592 KB
subtask2-14.txt 1462 ms 206464 KB
subtask2-15.txt 1468 ms 206464 KB
subtask2-16.txt 1457 ms 206464 KB