Submission #969335

#TimeUsernameProblemLanguageResultExecution timeMemory
969335MinaRagy06Boat (APIO16_boat)C++17
0 / 100
2 ms1368 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long 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; } }; int main() { ios_base::sync_with_stdio(0), cin.tie(0); 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]); } 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 = 0; j <= n; j++) { dp[m][j] = 1; } v.push_back(v.back() + 1); for (int i = m - 1; i >= 0; i--) { for (int j = 0; j <= n; j++) { dp[i][j] = dp[i + 1][j]; for (auto k : gud[i]) { if (j <= k) { dp[i][j] += dp[i + 1][k] * (v[i + 1] - v[i]); break; } } } } cout << dp[0][0] - 1 << '\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...