Submission #1347704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1347704		iamhereforfun	Boat (APIO16_boat)	C++20	In queue	0 ms	0 KiB

boat

// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 1e3 + 5;
const int M = 1 << 10;
const int K = 19;
const int LG = 11;
const int INF = 1e9 + 5;
const int C = 26;
const int B = 1000;
const int MOD = 1e9 + 7;

int n;
vector<int> v;
vector<pair<int, int>> boats;
long long dp[N][N], inv[N], ans;

long long pw(long long a, long long b = MOD - 2)
{
    long long ans = 1;
    while (b)
    {
        if (b & 1)
            ans *= a;
        a *= a;
        a %= MOD;
        ans %= MOD;
        b >>= 1;
    }
    return ans;
}

inline void solve()
{
    cin >> n;
    for (int x = 0; x <= n; x++)
    {
        inv[x] = pw(x);
    }
    for (int x = 0; x < n; x++)
    {
        int a, b;
        cin >> a >> b;
        b++;
        v.push_back(b);
        v.push_back(a);
        boats.push_back({a, b});
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    ans = 0;
    for (int x = 0; x < n; x++)
    {
        auto [a, b] = boats[x];
        long long cur = 0;
        a = lower_bound(v.begin(), v.end(), a) - v.begin();
        b = lower_bound(v.begin(), v.end(), b) - v.begin();
        for (int y = 0; y < v.size() - 1; y++)
        {
            long long nxt = cur;
            for (int z = 1; z <= x + 1; z++)
            {
                nxt += dp[y][z];
            }
            if (a <= y && y < b)
            {
                for (int z = x + 1; z >= 2; z--)
                {
                    dp[y][z] += dp[y][z - 1] * (v[y + 1] - v[y] - z + 1) % MOD * inv[z] % MOD;
                }
                dp[y][1] += 1LL * (cur + 1) * (v[y + 1] - v[y]);
                dp[y][1] %= MOD;
                // cout << dp[y][1] << " " << v[y] << " " << v[y + 1] << "\n";
            }
            cur = nxt;
        }
    }
    for (int x = 0; x < v.size(); x++)
    {
        for (int y = 0; y < v.size(); y++)
        {
            ans += dp[x][y];
            ans %= MOD;
        }
    }
    cout << ans << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}