답안 #720108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720108	2023-04-07T12:18:03 Z	Forested	Boat (APIO16_boat)	C++17	100 / 100	870 ms	4368 KB

boat

#ifndef LOCAL
#define FAST_IO
#endif

// ============
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define ALL(x) begin(x), end(x)

using namespace std;

using u32 = unsigned int;
using u64 = unsigned long long;
using i32 = signed int;
using i64 = signed long long;
using f64 = double;
using f80 = long double;

template <typename T>
using Vec = vector<T>;

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

template <typename T>
Vec<tuple<i32, i32, T>> runlength(const Vec<T> &a) {
    if (a.empty()) {
        return Vec<tuple<i32, i32, T>>();
    }
    Vec<tuple<i32, i32, T>> ret;
    i32 prv = 0;
    REP(i, 1, a.size()) {
        if (a[i - 1] != a[i]) {
            ret.emplace_back(prv, i, a[i - 1]);
            prv = i;
        }
    }
    ret.emplace_back(prv, (i32)a.size(), a.back());
    return ret;
}

#ifdef INT128

using u128 = __uint128_t;
using i128 = __int128_t;

istream &operator>>(istream &is, i128 &x) {
    i64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, i128 x) {
    os << (i64)x;
    return os;
}
istream &operator>>(istream &is, u128 &x) {
    u64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, u128 x) {
    os << (u64)x;
    return os;
}

#endif

[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;
struct SetUpIO {
    SetUpIO() {
#ifdef FAST_IO
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
#endif
        cout << fixed << setprecision(15);
    }
} set_up_io;
// ============

#ifdef DEBUGF
#else
#define DBG(x) (void)0
#endif

// ============

#include <cassert>
#include <iostream>
#include <type_traits>

// ============

constexpr bool is_prime(unsigned n) {
    if (n == 0 || n == 1) {
        return false;
    }
    for (unsigned i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

constexpr unsigned mod_pow(unsigned x, unsigned y, unsigned mod) {
    unsigned ret = 1, self = x;
    while (y != 0) {
        if (y & 1) {
            ret = (unsigned) ((unsigned long long) ret * self % mod);
        }
        self = (unsigned) ((unsigned long long) self * self % mod);
        y /= 2;
    }
    return ret;
}

template <unsigned mod>
constexpr unsigned primitive_root() {
    static_assert(is_prime(mod), "`mod` must be a prime number.");
    if (mod == 2) {
        return 1;
    }

    unsigned primes[32] = {};
    int it = 0;
    {
        unsigned m = mod - 1;
        for (unsigned i = 2; i * i <= m; ++i) {
            if (m % i == 0) {
                primes[it++] = i;
                while (m % i == 0) {
                    m /= i;
                }
            }
        }
        if (m != 1) {
            primes[it++] = m;
        }
    }
    for (unsigned i = 2; i < mod; ++i) {
        bool ok = true;
        for (int j = 0; j < it; ++j) {
            if (mod_pow(i, (mod - 1) / primes[j], mod) == 1) {
                ok = false;
                break;
            }
        }
        if (ok)
            return i;
    }
    return 0;
}

// y >= 1
template <typename T>
constexpr T safe_mod(T x, T y) {
    x %= y;
    if (x < 0) {
        x += y;
    }
    return x;
}

// y != 0
template <typename T>
constexpr T floor_div(T x, T y) {
    if (y < 0) {
        x *= -1;
        y *= -1;
    }
    if (x >= 0) {
        return x / y;
    } else {
        return -((-x + y - 1) / y);
    }
}

// y != 0
template <typename T>
constexpr T ceil_div(T x, T y) {
    if (y < 0) {
        x *= -1;
        y *= -1;
    }
    if (x >= 0) {
        return (x + y - 1) / y;
    } else {
        return -(-x / y);
    }
}
// ============

template <unsigned mod>
class ModInt {
    static_assert(mod != 0, "`mod` must not be equal to 0.");
    static_assert(
        mod < (1u << 31),
        "`mod` must be less than (1u << 31) = 2147483648.");

    unsigned val;

public:
    static constexpr unsigned get_mod() {
        return mod;
    }
    
    constexpr ModInt() : val(0) {}
    template <typename T, std::enable_if_t<std::is_signed_v<T>> * = nullptr>
    constexpr ModInt(T x) : val((unsigned) ((long long) x % (long long) mod + (x < 0 ? mod : 0))) {}
    template <typename T, std::enable_if_t<std::is_unsigned_v<T>> * = nullptr>
    constexpr ModInt(T x) : val((unsigned) (x % mod)) {}

    static constexpr ModInt raw(unsigned x) {
        ModInt<mod> ret;
        ret.val = x;
        return ret;
    }

    constexpr unsigned get_val() const {
        return val;
    }

    constexpr ModInt operator+() const {
        return *this;
    }
    constexpr ModInt operator-() const {
        return ModInt<mod>(0u) - *this;
    }

    constexpr ModInt &operator+=(const ModInt &rhs) {
        val += rhs.val;
        if (val >= mod)
            val -= mod;
        return *this;
    }
    constexpr ModInt &operator-=(const ModInt &rhs) {
        if (val < rhs.val)
            val += mod;
        val -= rhs.val;
        return *this;
    }
    constexpr ModInt &operator*=(const ModInt &rhs) {
        val = (unsigned long long)val * rhs.val % mod;
        return *this;
    }
    constexpr ModInt &operator/=(const ModInt &rhs) {
        val = (unsigned long long)val * rhs.inv().val % mod;
        return *this;
    }

    friend constexpr ModInt operator+(const ModInt &lhs, const ModInt &rhs) {
        return ModInt<mod>(lhs) += rhs;
    }
    friend constexpr ModInt operator-(const ModInt &lhs, const ModInt &rhs) {
        return ModInt<mod>(lhs) -= rhs;
    }
    friend constexpr ModInt operator*(const ModInt &lhs, const ModInt &rhs) {
        return ModInt<mod>(lhs) *= rhs;
    }
    friend constexpr ModInt operator/(const ModInt &lhs, const ModInt &rhs) {
        return ModInt<mod>(lhs) /= rhs;
    }

    constexpr ModInt pow(unsigned long long x) const {
        ModInt<mod> ret = ModInt<mod>::raw(1);
        ModInt<mod> self = *this;
        while (x != 0) {
            if (x & 1)
                ret *= self;
            self *= self;
            x >>= 1;
        }
        return ret;
    }
    constexpr ModInt inv() const {
        static_assert(is_prime(mod), "`mod` must be a prime number.");
        assert(val != 0);
        return this->pow(mod - 2);
    }

    friend std::istream &operator>>(std::istream &is, ModInt<mod> &x) {
        long long val;
        is >> val;
        x.val = val % mod + (val < 0 ? mod : 0);
        return is;
    }

    friend std::ostream &operator<<(std::ostream &os, const ModInt<mod> &x) {
        os << x.val;
        return os;
    }

    friend bool operator==(const ModInt &lhs, const ModInt &rhs) {
        return lhs.val == rhs.val;
    }
    
    friend bool operator!=(const ModInt &lhs, const ModInt &rhs) {
        return lhs.val != rhs.val;
    }
};

[[maybe_unused]] constexpr unsigned mod998244353 = 998244353;
[[maybe_unused]] constexpr unsigned mod1000000007 = 1000000007;

// ============
using Mint = ModInt<mod1000000007>;

int main() {
    i32 n;
    cin >> n;
    Vec<i32> a(n), b(n);
    REP(i, n) {
        cin >> a[i] >> b[i];
        ++b[i];
    }
    
    Vec<i32> c;
    c.reserve(2 * n);
    REP(i, n) {
        c.push_back(a[i]);
        c.push_back(b[i]);
    }
    sort(ALL(c));
    c.erase(unique(ALL(c)), c.end());
    REP(i, n) {
        a[i] = (i32)(lower_bound(ALL(c), a[i]) - c.begin());
        b[i] = (i32)(lower_bound(ALL(c), b[i]) - c.begin());
    }
    Vec<i32> lens(c.size() - 1);
    REP(i, c.size() - 1) {
        lens[i] = c[i + 1] - c[i];
    }
    
    Vec<Mint> inv(n + 1);
    REP(i, 1, n + 1) {
        inv[i] = Mint(i).inv();
    }
    
    Vec<i32> nd(lens.size(), 0);
    REP(i, n) {
        REP(j, a[i], b[i]) {
            ++nd[j];
        }
    }
    
    Vec<Vec<Mint>> pre(lens.size(), Vec<Mint>(n + 1));
    REP(i, lens.size()) {
        i32 l = lens[i];
        REP(j, 1, nd[i] + 1) {
            Mint p(l);
            REP(k, 1, min(l, j) + 1) {
                if (k >= 2) {
                    p *= Mint::raw(l - k + 1);
                    p *= inv[k];
                    p *= Mint::raw(j - k + 1);
                    p *= inv[k - 1];
                }
                pre[i][j] += p;
            }
        }
    }
    
    Vec<Vec<Mint>> dp(n + 1, Vec<Mint>(c.size()));
    REP(i, c.size()) {
        dp[0][i] = Mint(1);
    }
    REP(i, n) {
        Vec<Mint> raw(lens.size());
        REP(j, a[i], b[i]) {
            i32 cnt = 0;
            PER(k, i + 1) {
                if (a[k] <= j && j < b[k]) {
                    ++cnt;
                }
                raw[j] += pre[j][cnt] * dp[k][j];
            }
        }
        REP(j, lens.size()) {
            dp[i + 1][j + 1] = dp[i + 1][j] + raw[j];
        }
    }
    Mint ans;
    REP(i, 1, n + 1) {
        ans += dp[i][lens.size()];
    }
    cout << ans << '\n';
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4308 KB	Output is correct
2	Correct	4 ms	4308 KB	Output is correct
3	Correct	6 ms	4308 KB	Output is correct
4	Correct	4 ms	4308 KB	Output is correct
5	Correct	5 ms	4308 KB	Output is correct
6	Correct	4 ms	4308 KB	Output is correct
7	Correct	4 ms	4308 KB	Output is correct
8	Correct	4 ms	4308 KB	Output is correct
9	Correct	4 ms	4308 KB	Output is correct
10	Correct	4 ms	4308 KB	Output is correct
11	Correct	4 ms	4320 KB	Output is correct
12	Correct	5 ms	4308 KB	Output is correct
13	Correct	6 ms	4308 KB	Output is correct
14	Correct	4 ms	4308 KB	Output is correct
15	Correct	5 ms	4308 KB	Output is correct
16	Correct	3 ms	980 KB	Output is correct
17	Correct	2 ms	980 KB	Output is correct
18	Correct	2 ms	980 KB	Output is correct
19	Correct	2 ms	980 KB	Output is correct
20	Correct	2 ms	980 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4308 KB	Output is correct
2	Correct	4 ms	4308 KB	Output is correct
3	Correct	6 ms	4308 KB	Output is correct
4	Correct	4 ms	4308 KB	Output is correct
5	Correct	5 ms	4308 KB	Output is correct
6	Correct	4 ms	4308 KB	Output is correct
7	Correct	4 ms	4308 KB	Output is correct
8	Correct	4 ms	4308 KB	Output is correct
9	Correct	4 ms	4308 KB	Output is correct
10	Correct	4 ms	4308 KB	Output is correct
11	Correct	4 ms	4320 KB	Output is correct
12	Correct	5 ms	4308 KB	Output is correct
13	Correct	6 ms	4308 KB	Output is correct
14	Correct	4 ms	4308 KB	Output is correct
15	Correct	5 ms	4308 KB	Output is correct
16	Correct	3 ms	980 KB	Output is correct
17	Correct	2 ms	980 KB	Output is correct
18	Correct	2 ms	980 KB	Output is correct
19	Correct	2 ms	980 KB	Output is correct
20	Correct	2 ms	980 KB	Output is correct
21	Correct	166 ms	3952 KB	Output is correct
22	Correct	163 ms	3996 KB	Output is correct
23	Correct	147 ms	3924 KB	Output is correct
24	Correct	166 ms	3900 KB	Output is correct
25	Correct	158 ms	3928 KB	Output is correct
26	Correct	205 ms	3824 KB	Output is correct
27	Correct	209 ms	3880 KB	Output is correct
28	Correct	205 ms	3796 KB	Output is correct
29	Correct	210 ms	3804 KB	Output is correct
30	Correct	5 ms	4180 KB	Output is correct
31	Correct	6 ms	4308 KB	Output is correct
32	Correct	5 ms	4180 KB	Output is correct
33	Correct	5 ms	4308 KB	Output is correct
34	Correct	6 ms	4180 KB	Output is correct
35	Correct	6 ms	4180 KB	Output is correct
36	Correct	6 ms	4180 KB	Output is correct
37	Correct	8 ms	4180 KB	Output is correct
38	Correct	5 ms	4180 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	468 KB	Output is correct
2	Correct	3 ms	468 KB	Output is correct
3	Correct	4 ms	468 KB	Output is correct
4	Correct	4 ms	468 KB	Output is correct
5	Correct	5 ms	468 KB	Output is correct
6	Correct	9 ms	468 KB	Output is correct
7	Correct	7 ms	468 KB	Output is correct
8	Correct	8 ms	468 KB	Output is correct
9	Correct	8 ms	404 KB	Output is correct
10	Correct	7 ms	468 KB	Output is correct
11	Correct	4 ms	468 KB	Output is correct
12	Correct	3 ms	468 KB	Output is correct
13	Correct	3 ms	468 KB	Output is correct
14	Correct	3 ms	468 KB	Output is correct
15	Correct	4 ms	468 KB	Output is correct
16	Correct	3 ms	340 KB	Output is correct
17	Correct	2 ms	340 KB	Output is correct
18	Correct	2 ms	340 KB	Output is correct
19	Correct	2 ms	340 KB	Output is correct
20	Correct	3 ms	340 KB	Output is correct

Subtask #4
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4308 KB	Output is correct
2	Correct	4 ms	4308 KB	Output is correct
3	Correct	6 ms	4308 KB	Output is correct
4	Correct	4 ms	4308 KB	Output is correct
5	Correct	5 ms	4308 KB	Output is correct
6	Correct	4 ms	4308 KB	Output is correct
7	Correct	4 ms	4308 KB	Output is correct
8	Correct	4 ms	4308 KB	Output is correct
9	Correct	4 ms	4308 KB	Output is correct
10	Correct	4 ms	4308 KB	Output is correct
11	Correct	4 ms	4320 KB	Output is correct
12	Correct	5 ms	4308 KB	Output is correct
13	Correct	6 ms	4308 KB	Output is correct
14	Correct	4 ms	4308 KB	Output is correct
15	Correct	5 ms	4308 KB	Output is correct
16	Correct	3 ms	980 KB	Output is correct
17	Correct	2 ms	980 KB	Output is correct
18	Correct	2 ms	980 KB	Output is correct
19	Correct	2 ms	980 KB	Output is correct
20	Correct	2 ms	980 KB	Output is correct
21	Correct	166 ms	3952 KB	Output is correct
22	Correct	163 ms	3996 KB	Output is correct
23	Correct	147 ms	3924 KB	Output is correct
24	Correct	166 ms	3900 KB	Output is correct
25	Correct	158 ms	3928 KB	Output is correct
26	Correct	205 ms	3824 KB	Output is correct
27	Correct	209 ms	3880 KB	Output is correct
28	Correct	205 ms	3796 KB	Output is correct
29	Correct	210 ms	3804 KB	Output is correct
30	Correct	5 ms	4180 KB	Output is correct
31	Correct	6 ms	4308 KB	Output is correct
32	Correct	5 ms	4180 KB	Output is correct
33	Correct	5 ms	4308 KB	Output is correct
34	Correct	6 ms	4180 KB	Output is correct
35	Correct	6 ms	4180 KB	Output is correct
36	Correct	6 ms	4180 KB	Output is correct
37	Correct	8 ms	4180 KB	Output is correct
38	Correct	5 ms	4180 KB	Output is correct
39	Correct	4 ms	468 KB	Output is correct
40	Correct	3 ms	468 KB	Output is correct
41	Correct	4 ms	468 KB	Output is correct
42	Correct	4 ms	468 KB	Output is correct
43	Correct	5 ms	468 KB	Output is correct
44	Correct	9 ms	468 KB	Output is correct
45	Correct	7 ms	468 KB	Output is correct
46	Correct	8 ms	468 KB	Output is correct
47	Correct	8 ms	404 KB	Output is correct
48	Correct	7 ms	468 KB	Output is correct
49	Correct	4 ms	468 KB	Output is correct
50	Correct	3 ms	468 KB	Output is correct
51	Correct	3 ms	468 KB	Output is correct
52	Correct	3 ms	468 KB	Output is correct
53	Correct	4 ms	468 KB	Output is correct
54	Correct	3 ms	340 KB	Output is correct
55	Correct	2 ms	340 KB	Output is correct
56	Correct	2 ms	340 KB	Output is correct
57	Correct	2 ms	340 KB	Output is correct
58	Correct	3 ms	340 KB	Output is correct
59	Correct	441 ms	4232 KB	Output is correct
60	Correct	402 ms	4352 KB	Output is correct
61	Correct	381 ms	4356 KB	Output is correct
62	Correct	437 ms	4244 KB	Output is correct
63	Correct	414 ms	4368 KB	Output is correct
64	Correct	859 ms	4312 KB	Output is correct
65	Correct	862 ms	4320 KB	Output is correct
66	Correct	870 ms	4312 KB	Output is correct
67	Correct	862 ms	4312 KB	Output is correct
68	Correct	868 ms	4312 KB	Output is correct
69	Correct	359 ms	4312 KB	Output is correct
70	Correct	359 ms	4368 KB	Output is correct
71	Correct	358 ms	4312 KB	Output is correct
72	Correct	383 ms	4312 KB	Output is correct
73	Correct	385 ms	4300 KB	Output is correct
74	Correct	62 ms	948 KB	Output is correct
75	Correct	57 ms	972 KB	Output is correct
76	Correct	62 ms	960 KB	Output is correct
77	Correct	62 ms	1076 KB	Output is correct
78	Correct	63 ms	960 KB	Output is correct

답안 #720108

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 22.0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 42.0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
22.0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
42.0 / 42.0