Submission #969342

#TimeUsernameProblemLanguageResultExecution timeMemory
969342MinaRagy06Boat (APIO16_boat)C++17
9 / 100
491 ms6492 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define SZ(x) (int) x.size() const int mod = 1e9 + 7; struct mint { int v; mint(long long x) { if (x >= mod) x %= mod; v = x; } mint() {v = 0;} mint& operator+=(mint b) { if ((v += b.v) >= mod) { v -= mod; } return *this; } mint& operator-=(mint b) { if ((v -= b.v) < 0) { v += mod; } return *this; } mint& operator*=(mint b) { v = 1ll * v * b.v % mod; return *this; } mint power(mint a, int b) { mint ans = 1; while (b) { if (b & 1) { ans *= a; } a *= a, b >>= 1; } return ans; } mint& operator/=(mint b) { v = 1ll * v * power(b, mod - 2).v % mod; return *this; } friend mint operator+(mint a, mint b) { return a += b; } friend mint operator-(mint a, mint b) { return a -= b; } friend mint operator*(mint a, mint b) { return a *= b; } friend mint operator/(mint a, mint b) { return a /= b; } friend istream& operator>>(istream &is, mint &a) { return is >> a.v; } friend ostream& operator<<(ostream &os, mint a) { return os << a.v; } }; const int N = 505; mint fact[N], inv[N]; mint nCr(int n, int r) { if (n < 0 || r < 0 || n - r < 0) return 0; // cout << "> " << n << ' ' << r << ' ' << fact[n] * inv[r] * inv[n - r] << '\n'; return fact[n] * inv[r] * inv[n - r]; } int main() { ios_base::sync_with_stdio(0), cin.tie(0); fact[0] = 1; for (int i = 1; i < N; i++) { fact[i] = fact[i - 1] * i; } inv[N - 1] = 1 / fact[N - 1]; for (int i = N - 2; i >= 0; i--) { inv[i] = inv[i + 1] * (i + 1); } int n; cin >> n; array<int, 2> a[n]; vector<int> v; for (int i = 0; i < n; i++) { cin >> a[i][0] >> a[i][1]; v.push_back(a[i][0]); v.push_back(a[i][1]); v.push_back(a[i][1] + 1); } sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); auto get = [&] (int x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); }; int m = v.size(); vector<int> gud[m]; for (int i = 0; i < n; i++) { int l = get(a[i][0]), r = get(a[i][1]); for (int j = l; j <= r; j++) { gud[j].push_back(i + 1); } } mint dp[m + 1][n + 1]; for (int j = 1; j <= n; j++) { dp[m][j] = 1; } for (int i = m - 1; i >= 0; i--) { int sz = gud[i].size(); mint dp2[sz + 1][sz + 1]; for (int j = sz - 1; j >= 0; j--) { for (int k = 1; k <= sz; k++) { dp2[j][k] += dp2[j + 1][k]; if (k == 1) { dp2[j][k] += dp[i + 1][gud[i][j]]; } else { dp2[j][k] += dp2[j + 1][k - 1]; } } } for (int j = 0; j <= n; j++) { int pos = SZ(gud[i]); for (int k = 0; k < SZ(gud[i]); k++) { if (j < gud[i][k]) { pos = k; break; } } dp[i][j] = dp[i + 1][j]; for (int k = 1; k <= SZ(gud[i]) - pos; k++) { // cout << k << ' ' << dp2[pos][k] << ' ' << v[i + 1] - v[i] << ' ' << k << ' ' << nCr(v[i + 1] - v[i], k) << '\n'; dp[i][j] += dp2[pos][k] * nCr(v[i + 1] - v[i], k); } } } // for (int i = 0; i < m; i++) { // for (int j = 0; j <= n; j++) { // cout << dp[i][j] << ' '; // } // cout << '\n'; // } cout << dp[0][0] << '\n'; 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...