oj.uz

Submission #404889

# Submission time Handle Problem Language Result Execution time Memory
404889 2021-05-15T08:43:55 Z Forested Boat (APIO16_boat) C++17
9 / 100
 707 ms 13184 KB 
// Template
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <tuple>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <array>
#include <cassert>
#include <cmath>
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll infll = 3003003003003003003LL;
template <typename T>
inline bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T> 
inline bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &element : vec) is >> element;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    for (int i = 0, vec_len = (int)vec.size(); i < vec_len; ++i) {
        os << vec[i] << (i + 1 == vec_len ? "" : " ");
    }
    return os;
}
struct IOSET {
    IOSET() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} ioset;

// Mod-Int
#include <iostream>

template <unsigned int mod>
struct ModInt {
    static_assert(mod >= 1 && mod < (1u << 31));
    
    unsigned int val;
    
    ModInt() : val(0) {}
    
    ModInt(long long x) : val(x < 0 ? x % mod + mod : (unsigned long long)x % mod) {}
    
    ModInt<mod> &operator+=(const ModInt<mod> &x) {
        val += x.val;
        if (val >= mod) val -= mod;
        return *this;
    }
    
    ModInt<mod> &operator-=(const ModInt<mod> &x) {
        if (val < x.val) val += mod;
        val -= x.val;
        return *this;
    }
    
    ModInt<mod> &operator*=(const ModInt<mod> &x) {
        unsigned long long s = (unsigned long long)val * x.val;
        val = (unsigned int)(s % mod);
        return *this;
    }
    
    ModInt<mod> operator+() const {
        return *this;
    }
    
    ModInt<mod> operator-() const {
        return ModInt<mod>(0u) - *this;
    }
    
    friend ModInt<mod> operator+(const ModInt<mod> &x, const ModInt<mod> &y) {
        return ModInt<mod>(x) += y;
    }
    
    friend ModInt<mod> operator-(const ModInt<mod> &x, const ModInt<mod> &y) {
        return ModInt<mod>(x) -= y;
    }
    
    friend ModInt<mod> operator*(const ModInt<mod> &x, const ModInt<mod> &y) {
        return ModInt<mod>(x) *= y;
    }
    
    friend std::istream &operator>>(std::istream &is, ModInt<mod> &x) {
        is >> x.val;
        // x.value %= mod;
        return is;
    }
    
    friend std::ostream &operator<<(std::ostream &os, const ModInt<mod> &x) {
        os << x.val;
        return os;
    }
    
    ModInt<mod> pow(unsigned long long x) const {
        ModInt<mod> res(1), s(*this);
        while (x) {
            if (x & 1) res *= s;
            s *= s;
            x >>= 1;
        }
        return res;
    }
    
    // --- prime number ---
    ModInt<mod> &operator/=(const ModInt<mod> &x) {
        *this *= x.pow(mod - 2);
        return *this;
    }
    
    friend ModInt<mod> operator/(const ModInt<mod> &x, const ModInt<mod> &y) {
        return ModInt<mod>(x) /= y;
    }
};

// Main
int main() {
    constexpr unsigned mod = 1000000007;
    using Mint = ModInt<mod>;
    
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    rep(i, n) {
        cin >> a[i] >> b[i];
        ++b[i];
    }
    
    vector<int> ps;
    ps.reserve(2 * n);
    rep(i, n) {
        ps.push_back(a[i]);
        ps.push_back(b[i]);
    }
    sort(all(ps));
    ps.erase(unique(all(ps)), ps.end());
    rep(i, n) {
        a[i] = lower_bound(all(ps), a[i]) - ps.begin();
        b[i] = lower_bound(all(ps), b[i]) - ps.begin();
    }
    
    int k = ps.size() - 1;
    
    vector<vector<Mint>> comb(k, vector<Mint>(n + 1));
    rep(i, k) {
        int d = ps[i + 1] - ps[i];
        Mint p(1);
        comb[i][0] = Mint(1);
        rep(j, 1, min(d, n) + 1) {
            p *= Mint(d - j + 1);
            p /= Mint(j);
            comb[i][j] = p;
        }
    }
    vector<vector<Mint>> comb1(k, vector<Mint>(n + 1));
    rep(i, k) {
        int d = ps[i + 1] - ps[i] - 1;
        Mint p(1);
        comb1[i][0] = Mint(1);
        rep(j, 1, min(d, n) + 1) {
            p *= Mint(d - j + 1);
            p /= Mint(j);
            comb1[i][j] = p;
        }
    }
    vector<vector<Mint>> comb2(k, vector<Mint>(n + 1));
    rep(i, k) {
        int d = ps[i + 1] - ps[i] - 2;
        if (d == -1) continue;
        Mint p(1);
        comb2[i][0] = Mint(1);
        rep(j, 1, min(d, n) + 1) {
            p *= Mint(d - j + 1);
            p /= Mint(j);
            comb2[i][j] = p;
        }
    }
    vector<vector<Mint>> combn(n + 1, vector<Mint>(n + 1));
    combn[0][0] = Mint(1);
    rep(i, 1, n + 1) rep(j, i + 1) {
        combn[i][j] += combn[i - 1][j];
        if (j != 0) combn[i][j] += combn[i - 1][j - 1];
    }
    vector<vector<Mint>> _sum(k, vector<Mint>(n + 1));
    rep(i, k) {
        int d = ps[i + 1] - ps[i];
        _sum[i][1] = Mint(d);
        rep(j, 2, min(d, n) + 1) {
            rep(l, 2, j + 1) {
                _sum[i][j] += comb[i][l] * combn[j][l] - Mint(2) * comb1[i][l] * combn[j][l] + comb2[i][l] * combn[j][l];
            }
        }
    }
    
    vector<vector<Mint>> dp(n + 1, vector<Mint>(k + 1)), sum(n + 1, vector<Mint>(k + 1));
    dp[0][0] = Mint(1);
    sum[0] = vector<Mint>(k + 1, Mint(1));
    rep(i, n) {
        dp[i + 1] = dp[i];
        sum[i + 1][0] = dp[i + 1][0];
        rep(j, 1, k + 1) {
            int d = ps[j] - ps[j - 1];
            int cnt = 0;
            for (int l = i; l >= 0; --l) {
                if (b[l] <= j - 1 || a[l] >= j) {
                    if (l == i) break;
                    continue;
                }
                if (++cnt > d) break;
                dp[i + 1][j] += _sum[j - 1][cnt] * sum[l][j - 1];
            }
            sum[i + 1][j] = sum[i + 1][j - 1] + dp[i + 1][j];
        }
    }
    
    cout << sum[n][k] - Mint(1) << '\n';
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 13124 KB Output is correct
2 Correct 627 ms 13116 KB Output is correct
3 Correct 658 ms 13120 KB Output is correct
4 Correct 665 ms 13116 KB Output is correct
5 Correct 707 ms 13120 KB Output is correct
6 Correct 650 ms 13120 KB Output is correct
7 Correct 614 ms 13112 KB Output is correct
8 Correct 614 ms 13172 KB Output is correct
9 Correct 625 ms 13124 KB Output is correct
10 Correct 616 ms 13120 KB Output is correct
11 Correct 607 ms 13116 KB Output is correct
12 Correct 625 ms 13124 KB Output is correct
13 Correct 621 ms 13120 KB Output is correct
14 Correct 630 ms 13184 KB Output is correct
15 Correct 618 ms 13116 KB Output is correct
16 Correct 107 ms 3396 KB Output is correct
17 Correct 119 ms 3588 KB Output is correct
18 Correct 127 ms 3448 KB Output is correct
19 Correct 116 ms 3484 KB Output is correct
20 Correct 113 ms 3484 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 13124 KB Output is correct
2 Correct 627 ms 13116 KB Output is correct
3 Correct 658 ms 13120 KB Output is correct
4 Correct 665 ms 13116 KB Output is correct
5 Correct 707 ms 13120 KB Output is correct
6 Correct 650 ms 13120 KB Output is correct
7 Correct 614 ms 13112 KB Output is correct
8 Correct 614 ms 13172 KB Output is correct
9 Correct 625 ms 13124 KB Output is correct
10 Correct 616 ms 13120 KB Output is correct
11 Correct 607 ms 13116 KB Output is correct
12 Correct 625 ms 13124 KB Output is correct
13 Correct 621 ms 13120 KB Output is correct
14 Correct 630 ms 13184 KB Output is correct
15 Correct 618 ms 13116 KB Output is correct
16 Correct 107 ms 3396 KB Output is correct
17 Correct 119 ms 3588 KB Output is correct
18 Correct 127 ms 3448 KB Output is correct
19 Correct 116 ms 3484 KB Output is correct
20 Correct 113 ms 3484 KB Output is correct
21 Incorrect 33 ms 12196 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 13124 KB Output is correct
2 Correct 627 ms 13116 KB Output is correct
3 Correct 658 ms 13120 KB Output is correct
4 Correct 665 ms 13116 KB Output is correct
5 Correct 707 ms 13120 KB Output is correct
6 Correct 650 ms 13120 KB Output is correct
7 Correct 614 ms 13112 KB Output is correct
8 Correct 614 ms 13172 KB Output is correct
9 Correct 625 ms 13124 KB Output is correct
10 Correct 616 ms 13120 KB Output is correct
11 Correct 607 ms 13116 KB Output is correct
12 Correct 625 ms 13124 KB Output is correct
13 Correct 621 ms 13120 KB Output is correct
14 Correct 630 ms 13184 KB Output is correct
15 Correct 618 ms 13116 KB Output is correct
16 Correct 107 ms 3396 KB Output is correct
17 Correct 119 ms 3588 KB Output is correct
18 Correct 127 ms 3448 KB Output is correct
19 Correct 116 ms 3484 KB Output is correct
20 Correct 113 ms 3484 KB Output is correct
21 Incorrect 33 ms 12196 KB Output isn't correct
22 Halted 0 ms 0 KB -