제출 #1345169

#제출 시각아이디문제언어결과실행 시간메모리
1345169cnam9Boat (APIO16_boat)C++20
100 / 100
79 ms4368 KiB
#include <iostream>
#include <algorithm>

using namespace std;

constexpr int N = 500;
constexpr int P = 1e9 + 7;

int n;
pair<int, int> intervals[N];
int poi[N * 2];
int inverse[N + 1];

inline int divide(int y, int x) {
    for (int k = P - 2; k; k >>= 1) {
        if (k & 1)
            y = (long long) y * x % P;
        x = (long long) x * x % P;
    }
    return y;
}

struct {
    int d;
    int b[N + 1];
    int c[N + 2];

    void init(int R) {
        b[0] = 1;
        for (int k = 1; k <= n; k++) {
            b[k] = (long long) (R + k) * b[k - 1] % P * inverse[k] % P;
        }
        d = n + 1;
    }

    operator int() {
        return c[1] - c[0];
    }

    void operator+=(int x) {
        for (int k = 0; k < d; k++) {
            c[k] = (c[k + 1] + (long long) x * b[k]) % P;
        }
        d--;
    }
} dp[2 * N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // freopen("input.txt", "r", stdin);

    cin >> n;

    for (int x = 1; x <= n; x++) {
        inverse[x] = divide(1, x);
    }

    for (int i = 0; i < n; i++) {
        auto &[l, r] = intervals[i];
        cin >> l >> r;
        r++;

        poi[i * 2] = l;
        poi[i * 2 + 1] = r;
    }
    sort(poi, poi + 2 * n);
    int m = unique(poi, poi + 2 * n) - poi - 1;

    for (int j = 0; j < m; j++) {
        dp[j].init(poi[j + 1] - poi[j]);
    }

    for (int i = 0; i < n; i++) {
        auto [l, r] = intervals[i];

        long long s = 1;
        int j = 0;
        for (; poi[j] < l; j++) {
            s += dp[j];
        }
        s %= P;

        for (; poi[j] < r; j++) {
            int t = (s + dp[j]) % P;
            dp[j] += s;
            s = t;
        }
    }

    long long res = 0;
    for (int j = 0; j < m; j++) {
        res += dp[j];
    }
    cout << (res % P + P) % P;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...