| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 263001 |
2020-08-13T11:46:54 Z |
KoD |
Boat (APIO16_boat) |
C++11 |
|
78 ms |
83680 KB |
/**
* @title Template
*/
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
template <class T, class U>
bool chmin(T &lhs, const U &rhs) {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
template <class T, class U>
bool chmax(T &lhs, const U &rhs) {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
/**
* @title Chmin/Chmax
*/
class range {
public:
class iterator {
private:
int64_t M_position;
public:
iterator(int64_t position) noexcept: M_position(position) { }
void operator ++ () noexcept { ++M_position; }
bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
int64_t operator * () const noexcept { return M_position; }
};
class reverse_iterator {
private:
int64_t M_position;
public:
reverse_iterator(int64_t position) noexcept: M_position(position) { }
void operator ++ () noexcept { --M_position; }
bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
int64_t operator * () const noexcept { return M_position; }
};
private:
const iterator M_first, M_last;
public:
range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
iterator begin() const noexcept { return M_first; }
iterator end() const noexcept { return M_last; }
reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); }
reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); }
};
/**
* @title Range
*/
#include <type_traits>
#include <iterator>
template <class T>
class rev_impl {
public:
using iterator = decltype(std::declval<T>().rbegin());
private:
const iterator M_begin;
const iterator M_end;
public:
rev_impl(T &&cont) noexcept: M_begin(cont.rbegin()), M_end(cont.rend()) { }
iterator begin() const noexcept { return M_begin; }
iterator end() const noexcept { return M_end; }
};
template <class T>
rev_impl<T> rev(T &&cont) {
return rev_impl<T>(std::forward<T>(cont));
}
/**
* @title Reverser
*/
#include <cstdint>
template <class Modulus>
class modular {
public:
using value_type = uint32_t;
using cover_type = uint64_t;
static constexpr value_type mod() { return Modulus::value(); }
template <class T>
static value_type normalize(T value_) noexcept {
if (value_ < 0) {
value_ = -value_;
value_ %= mod();
if (value_ == 0) return 0;
return mod() - value_;
}
return value_ % mod();
}
private:
value_type value;
public:
modular() noexcept : value(0) { }
template <class T>
explicit modular(T value_) noexcept : value(normalize(value_)) { }
template <class T>
explicit operator T() const noexcept { return static_cast<T>(value); }
value_type get() const noexcept { return value; }
modular operator - () const noexcept { return modular(mod() - value); }
modular operator ~ () const noexcept { return inverse(); }
value_type &extract() noexcept { return value; }
modular inverse() const noexcept { return power(mod() - 2); }
modular power(cover_type exp) const noexcept {
modular res(1), mult(*this);
while (exp > 0) {
if (exp & 1) res *= mult;
mult *= mult;
exp >>= 1;
}
return res;
}
modular operator + (const modular &rhs) const noexcept { return modular(*this) += rhs; }
modular& operator += (const modular &rhs) noexcept {
if ((value += rhs.value) >= mod()) value -= mod();
return *this;
}
modular operator - (const modular &rhs) const noexcept { return modular(*this) -= rhs; }
modular& operator -= (const modular &rhs) noexcept {
if ((value += mod() - rhs.value) >= mod()) value -= mod();
return *this;
}
modular operator * (const modular &rhs) const noexcept { return modular(*this) *= rhs; }
modular& operator *= (const modular &rhs) noexcept {
value = (cover_type) value * rhs.value % mod();
return *this;
}
modular operator / (const modular &rhs) const noexcept { return modular(*this) /= rhs; }
modular& operator /= (const modular &rhs) noexcept { return (*this) *= rhs.inverse(); }
bool zero() const noexcept { return value == 0; }
bool operator == (const modular &rhs) const noexcept { return value == rhs.value; }
bool operator != (const modular &rhs) const noexcept { return value != rhs.value; }
friend std::ostream& operator << (std::ostream &stream, const modular &rhs) { return stream << rhs.value; }
friend modular power(modular val, cover_type exp) noexcept { return val.power(exp); }
friend modular inverse(modular val) noexcept { return val.inverse(); }
};
template <uint32_t Val>
struct modulus_impl { static constexpr uint32_t value() noexcept { return Val; } };
template <uint32_t Val>
using mint32_t = modular<modulus_impl<Val>>;
struct runtime_mod { static uint32_t &value() noexcept { static uint32_t val = 0; return val; } };
using rmint32_t = modular<runtime_mod>;
/**
* @title Modint
*/
#include <cstddef>
template <class T, size_t N>
class factorials {
public:
using value_type = T;
static constexpr size_t size = N;
public:
std::array<value_type, size + 1> fact{};
std::array<value_type, size + 1> fact_inv{};
factorials() {
fact.front() = value_type(1);
for (size_t i = 1; i <= size; ++i) {
fact[i] = fact[i - 1] * value_type(i);
}
fact_inv.back() = ~fact.back();
for (size_t i = size; i > 0; --i) {
fact_inv[i - 1] = fact_inv[i] * value_type(i);
}
}
value_type operator () (size_t n, size_t r) const {
return fact[n] * fact_inv[n - r] * fact_inv[r];
}
};
/**
* @title Factorial
*/
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;
using m32 = mint32_t<1000000007>;
factorials<m32, 500> fact;
int main() {
size_t N;
std::cin >> N;
std::vector<i32> L(N), R(N);
std::vector<i32> comp;
comp.reserve(2 * N);
for (auto i: range(0, N)) {
std::cin >> L[i] >> R[i];
++R[i];
comp.push_back(L[i]);
comp.push_back(R[i]);
}
std::sort(comp.begin(), comp.end());
comp.erase(std::unique(comp.begin(), comp.end()), comp.end());
const i32 size = comp.size() - 1;
std::vector<i32> len(size);
for (auto i: range(0, size)) {
len[i] = comp[i + 1] - comp[i];
}
for (auto i: range(0, N)) {
L[i] = std::distance(comp.cbegin(), std::lower_bound(comp.cbegin(), comp.cend(), L[i]));
R[i] = std::distance(comp.cbegin(), std::lower_bound(comp.cbegin(), comp.cend(), R[i]));
}
std::vector<std::vector<m32>> dp(size);
std::vector<std::vector<m32>> coeff(size);
for (auto i: range(0, size)) {
dp[i].resize(len[i] + 1);
coeff[i].resize(len[i] + 1);
m32 cur(1);
for (auto j: range(1, len[i] + 1)) {
cur *= m32(len[i] - j + 1);
coeff[i][j] = cur * fact.fact_inv[j];
}
}
for (auto i: range(0, N)) {
m32 sum;
for (auto j: range(0, L[i])) {
for (auto k: range(1, len[j] + 1)) {
sum += dp[j][k] * coeff[j][k];
}
}
for (auto j: range(L[i], R[i])) {
m32 add;
for (auto k: range(1, len[j] + 1)) {
add += dp[j][k] * coeff[j][k];
}
for (auto k: range(1, len[j])) {
dp[j][k + 1] += dp[j][k];
}
dp[j][1] += sum + m32(1);
sum += add;
}
}
m32 ans;
for (auto j: range(0, size)) {
for (auto k: range(1, len[j] + 1)) {
ans += dp[j][k] * coeff[j][k];
}
}
std::cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
16384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
16384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
78 ms |
83680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
16384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
