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>
typedef long long ll;
using namespace std;
const ll MAX = 1007, MOD = 1E9 + 7;
ll L[MAX], R[MAX], F[MAX], IF[MAX], C[MAX], all[MAX], temp[MAX];
vector<int> S[MAX];
ll Pow(ll N, ll K) {
ll ret = 1;
while (K) {
if (K & 1) ret = ret * N % MOD;
N = N * N % MOD;
K >>= 1LL;
}
return ret;
}
ll Comb(ll N, ll K) {
ll ret = IF[K];
for (ll j = N; j > N - K; --j) ret = (ret * j) % MOD;
return ret;
}
int main() {
F[0] = IF[0] = 1;
for (ll i = 1; i < MAX; ++i) {
F[i] = F[i - 1] * i % MOD;
IF[i] = Pow(F[i], MOD - 2);
}
ios::sync_with_stdio(0); cin.tie(0);
int N;
cin >> N;
vector<int> T;
for (int i = 1; i <= N; ++i) {
cin >> L[i] >> R[i];
T.push_back(L[i]);
T.push_back(R[i] + 1);
}
T.push_back(0);
sort(T.begin(), T.end());
T.erase(unique(T.begin(), T.end()), T.end());
for (int i = 1; i <= N; ++i) {
int l = lower_bound(T.begin(), T.end(), L[i]) - T.begin();
int r = lower_bound(T.begin(), T.end(), R[i] + 1) - T.begin();
for (int j = l; j < r; ++j) S[j].push_back(i);
}
all[0] = 1;
for (int i = 1; i + 1 < T.size(); ++i) {
memset(temp, 0, sizeof(temp));
ll z = T[i + 1] - T[i];
ll pv = 0, idx = 0;
for (int a = 0; a < S[i].size(); ++a) C[a] = Comb(z + a, a + 1);
for (int a = 0; a < S[i].size(); ++a) {
while (idx < S[i][a]) pv = (pv + all[idx++]) % MOD;
for (int b = a; b < S[i].size(); ++b) {
temp[S[i][b]] = (temp[S[i][b]] + pv * C[b - a]) % MOD;
}
pv = 0;
}
for (int j = 0; j < MAX; ++j) all[j] = (all[j] + temp[j]) % MOD;
}
ll ans = accumulate(all + 1, all + MAX, 0LL) % MOD;
cout << ans;
return 0;
}
Compilation message (stderr)
boat.cpp: In function 'int main()':
boat.cpp:52:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i = 1; i + 1 < T.size(); ++i) {
| ~~~~~~^~~~~~~~~~
boat.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int a = 0; a < S[i].size(); ++a) C[a] = Comb(z + a, a + 1);
| ~~^~~~~~~~~~~~~
boat.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int a = 0; a < S[i].size(); ++a) {
| ~~^~~~~~~~~~~~~
boat.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int b = a; b < S[i].size(); ++b) {
| ~~^~~~~~~~~~~~~
# | 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... |