Contest Duration: ~ (local time) (90 minutes) Back to Home

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"

/**
*/
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);
array<mint<MOD>, K> x = {{ 1 }};
REP (i, d) {
if (t[i] < middle) {
auto f = segtree.range_concat(s[i], t[i]);
} 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);
} else if (s[i] < middle and middle <= t[i]) {
auto right = segtree.range_concat(0, t[i] - middle);
}
}

REP (i, d) {
}
return 0;
}
```

#### Submission Info

Submission Time 2019-12-19 00:56:25+0900 D - ぴょんぴょんトレーニング kimiyuki C++14 (GCC 5.4.1) 100 10517 Byte AC 1468 ms 206592 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Case Name Status Exec Time Memory