#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const int N = 100;
int n, l[N + 5], r[N + 5], C[2 * N + 5][N + 5], dp[N + 5][2 * N + 5][N + 5];
vector<int> v;
ll modPow(ll a, ll b) {
if (b == 0) return 1;
ll ret = modPow(a, b / 2);
ret *= ret;
ret %= MOD;
if (b % 2) {
ret *= a;
ret %= MOD;
}
return ret;
}
ll modDivide(ll a, ll b) {
return (a * modPow(b, MOD - 2)) % MOD;
}
void beautify() {
{ // filling v
set<int> s;
for (int i = 0; i < n; i++) {
if (s.find(l[i]) == s.end()) {
s.insert(l[i]);
v.push_back(l[i]);
}
if (s.find(r[i]) == s.end()) {
s.insert(r[i]);
v.push_back(r[i]);
}
}
sort(v.begin(), v.end());
}
for (int i = 0; i + 1 < v.size(); i++) {
int len = v[i + 1] - v[i] + (i + 2 == v.size());
ll a, b;
C[i][0] = a = b = 1;
for (int j = 1; j <= min(N, len); j++) {
a *= len - j + 1;
a %= MOD;
b *= j;
b %= MOD;
C[i][j] = modDivide(a, b);
// cout << len << ' ' << j << ' ' << C[i][j] << endl;
}
}
}
int brutus(int i, int j, int k) {
if (j + 1 >= v.size() or k > v[j + 1] - v[j] + (j + 2 == v.size())) return 0;
if (i >= n) return C[j][k];
if (dp[i][j][k] != -1) return dp[i][j][k];
ll ret = 0;
ret = brutus(i + 1, j, k);
ret += (brutus(i, j + 1, 0) * C[j][k]) % MOD;
ret %= MOD;
if (i < n and l[i] <= v[j] and v[j + 1] <= r[i]) {
ret += brutus(i + 1, j, k + 1);
ret %= MOD;
}
dp[i][j][k] = ret;
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// cout << modDivide(169, 1) << endl;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> l[i] >> r[i];
}
beautify();
memset(dp, -1, sizeof dp);
int ans = brutus(0, 0, 0);
ans -= 1;
if (ans < 0) ans += MOD;
cout << ans << '\n';
return 0;
}
Compilation message
boat.cpp: In function 'void beautify()':
boat.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i = 0; i + 1 < v.size(); i++) {
| ~~~~~~^~~~~~~~~~
boat.cpp:48:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | int len = v[i + 1] - v[i] + (i + 2 == v.size());
| ~~~~~~^~~~~~~~~~~
boat.cpp: In function 'int brutus(int, int, int)':
boat.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if (j + 1 >= v.size() or k > v[j + 1] - v[j] + (j + 2 == v.size())) return 0;
| ~~~~~~^~~~~~~~~~~
boat.cpp:63:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if (j + 1 >= v.size() or k > v[j + 1] - v[j] + (j + 2 == v.size())) return 0;
| ~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
9292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
