This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double;
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 7;
ll inv[505] = {0, 1};
int n;
vector<int> cmp;
int a[505], b[505];
ll a_Ijk[2][1005][505]; // i' < i, j' = j, k' = k
ll b_ij[2][1005]; //i' < i, j' < j, k' arb
ll ans;
int main(){
fio;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
++b[i];
cmp.pp(a[i]); cmp.pp(b[i]);
}
for(int i = 2; i <= n; i++) {
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
debug("inv[%d] = %lld\n", i, inv[i]);
}
sort(all(cmp)); cmp.erase(unique(all(cmp)), cmp.end());
int d = szz(cmp);
for(int i = 1; i <= n; i++) {
a[i] = lb(all(cmp), a[i]) - cmp.begin() + 1;
b[i] = lb(all(cmp), b[i]) - cmp.begin() + 1;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j < d; j++) {
b_ij[i & 1][j] = (b_ij[~i & 1][j] + b_ij[i & 1][j-1] + mod - b_ij[~i & 1][j-1]) % mod;
for(int k = 1; k <= n; k++) {
a_Ijk[i & 1][j][k] = a_Ijk[~i & 1][j][k];
ll dp = 0;
if(a[i] <= j && j < b[i]) {
ll len = cmp[j] - cmp[j-1];
if(k == 1) {
dp = (1 + b_ij[~i & 1][j-1]) * len % mod;
}else{
dp = a_Ijk[~i & 1][j][k-1] * (len - k + 1) % mod * inv[k] % mod;
}
}
(a_Ijk[i & 1][j][k] += dp) %= mod;
b_ij[i & 1][j] += dp;
ans += dp;
}
b_ij[i & 1][j] %= mod;
}
}
cout << ans % mod << endl;
}
Compilation message (stderr)
boat.cpp: In function 'int main()':
boat.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
boat.cpp:56:9: note: in expansion of macro 'debug'
56 | debug("inv[%d] = %lld\n", i, inv[i]);
| ^~~~~
# | 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... |