#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(x, y) uniform_int_distribution<int>(x, y)(rng)
ll mod(ll a, ll b=(ll)P) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
ll g = a; x = 1, y = 0;
if(b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
return g;
}
ll inv(ll a, ll m=(ll)P) {
ll x, y; ll g = ext_gcd(a, m, x, y);
if(g > 1) return -1;
return mod(x, m);
}
int N;
int input[2][1000];
vector <ll> dp[2][2000];
set <int> ms;
vector <pii> A;
vector <int> len;
int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
cin >> N;
for(int i=1;i<=N;i++)
cin >> input[0][i] >> input[1][i];
ms.insert(0);
for(int i=1;i<=N;i++)
ms.insert(input[0][i]), ms.insert(input[1][i]);
auto it = ms.begin();
while(it!=ms.end()) {
int now = *it;
it++;
A.push_back({now, now});
if(it!=ms.end() && now+1 <= *it-1)
A.push_back({now+1, *it-1});
}
for(pii x : A)
len.push_back(x.se-x.fi+1);
for(int i=0;i<A.size();i++)
dp[0][i].push_back(1);
for(int i=1;i<=N;i++){
dp[i&1][0].clear();
dp[i&1][0].push_back(dp[(i-1)&1][0][0]);
for(int j=1;j<A.size();j++){
dp[i&1][j].clear();
dp[i&1][j].push_back(dp[i&1][j-1][0]+dp[(i-1)&1][j][0]-dp[(i-1)&1][j-1][0]);
if(A[j].fi > input[1][i] || input[0][i] > A[j].se)
continue;
dp[i&1][j].push_back(dp[(i-1)&1][j-1][0]);
for(int k=2;k<min((int)dp[(i-1)&1][j].size()+1, len[j]+1);k++)
dp[i&1][j].push_back(mod(mod((len[j]-k+1)*inv(k))*dp[(i-1)&1][j][k-1]));
for(int k=1;k<dp[i&1][j].size();k++)
dp[i&1][j][0] = mod(dp[i&1][j][0] + dp[i&1][j][k]);
}
/*
for(int j=0;j<A.size();j++)
cout << dp[i&1][j];
cout << endl;
*/
}
cout << dp[N&1][A.size()-1][0]-1;
return 0;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i=0;i<A.size();i++)
| ~^~~~~~~~~
boat.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int j=1;j<A.size();j++){
| ~^~~~~~~~~
boat.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int k=1;k<dp[i&1][j].size();k++)
| ~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
