This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int MAXN = (int)1e3 + 5;
const int MOD = (int)1e9 + 7;
int dp[2][MAXN][MAXN];
int mem[MAXN][MAXN];
vector<int> T;
pii arr[MAXN];
int rev[MAXN];
int n;
void addMod(int &a, int b, int m = MOD) {
a += b;
if (m <= a) {
a -= m;
}
}
void mulMod(int &a, int b, int m = MOD) {
a = (a * 1ll * b) % m;
}
int binPow(int a, int b) {
int ret = 1;
while (b > 0) {
if (b & 1) {
mulMod(ret, a);
}
mulMod(a, a);
b >>= 1;
}
return ret;
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d %d", &arr[i].fi, &arr[i].se);
T.pb(arr[i].fi);
T.pb(arr[i].se + 1);
}
T.pb(0);
sort(all(T));
T.resize(unique(all(T)) - T.begin());
for (int i = 1; i <= n; ++i) {
arr[i].fi = lower_bound(all(T), arr[i].fi) - T.begin();
arr[i].se = lower_bound(all(T), arr[i].se + 1) - T.begin();
}
for (int i = 0; i <= n; ++i) {
rev[i] = binPow(i, MOD - 2);
}
for (int i = 0; i + 1 < T.size(); ++i) {
int x = T[i + 1] - T[i];
mem[i][0] = 1;
for (int j = 1; j <= n; ++j) {
if (j > x) {
mem[i][j] = 0;
continue;
}
int tmp = mem[i][j - 1];
mulMod(tmp, x - j + 1);
mulMod(tmp, rev[j]);
mem[i][j] = tmp;
}
}
dp[0][0][0] = 1;
for (int i = 1; i <= n; ++i) {
int p = 0, w = 0;
for (int c = arr[i].fi; c < arr[i].se; ++c) {
for (int cnt = 1; cnt <= i; ++cnt) {
addMod(dp[1][c][cnt], dp[0][c][cnt - 1]);
}
while (p < c) {
for (int cnt = 0; cnt <= i; ++cnt) {
int tmp = dp[0][p][cnt];
mulMod(tmp, mem[p][cnt]);
addMod(w, tmp);
}
++p;
}
addMod(dp[1][c][1], w);
}
for (int c = 0; c < T.size(); ++c) {
for (int cnt = 0; cnt <= i; ++cnt) {
addMod(dp[0][c][cnt], dp[1][c][cnt]);
dp[1][c][cnt] = 0;
}
}
}
int ans = 0;
for (int c = 0; c + 1 < T.size(); ++c) {
for (int cnt = 1; cnt <= n; ++cnt) {
int tmp = dp[0][c][cnt];
mulMod(tmp, mem[c][cnt]);
addMod(ans, tmp);
}
}
printf("%d\n", ans);
}
int main() {
int tt = 1;
while (tt--) {
solve();
}
return 0;
}
Compilation message (stderr)
boat.cpp: In function 'void solve()':
boat.cpp:87:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i + 1 < T.size(); ++i) {
~~~~~~^~~~~~~~~~
boat.cpp:127:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int c = 0; c < T.size(); ++c) {
~~^~~~~~~~~~
boat.cpp:137:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int c = 0; c + 1 < T.size(); ++c) {
~~~~~~^~~~~~~~~~
boat.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
boat.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &arr[i].fi, &arr[i].se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |