| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 679221 | bebra | Boat (APIO16_boat) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << #x << ": " << x << endl;
struct Seg {
int l;
int r;
bool empty() const {
return r - l + 1 <= 0;
}
bool operator<(const Seg& other) const {
return tie(l, r) < tie(other.l, other.r);
}
bool operator==(const Seg& other) const {
return tie(l, r) == tie(other.l, other.r);
}
friend Seg intersect(const Seg& lhs, const Seg& rhs) {
return {max(lhs.l, rhs.l), min(lhs.r, rhs.r)};
}
};
const int MOD = 1e9 + 7;
const int INV2 = 500000004;
int add(int a, int b) {
int res = a + b;
if (res >= MOD) res -= MOD;
return res;
}
int mul(long long a, int b) {
return a * b % MOD;
}
const int MAX_N = 500 + 1;
Seg segs[MAX_N];
vector<Seg> states[MAX_N];
vector<int> dp[MAX_N];
int main_idx[MAX_N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> segs[i].l >> segs[i].r;
states[i].push_back(segs[i]);
}
segs[0] = {-1, -1};
states[0].emplace_back(-1, -1);
dp[0].assign(1, 1);
int ans = 0;
for (int i = 1; i <= n; ++i) {
vector<int> ls;
vector<int> rs;
for (int j = 1; j <= n; ++j) {
if (segs[j].l >= segs[i].l) {
ls.push_back(segs[j].l);
}
if (segs[j].r <= segs[i].r) {
rs.push_back(segs[j].r);
}
}
sort(ls.begin(), ls.end());
ls.resize(unique(ls.begin(), ls.end()) - ls.begin());
sort(rs.begin(), rs.end());
rs.resize(unique(rs.begin(), rs.end()) - rs.begin());
for (auto l : ls) {
for (auto r : rs) {
if (l <= r) {
states[i].emplace_back(l, r);
}
}
}
for (auto l1 : ls) {
for (auto l2 : ls) {
if (l2 - 1 >= l1) {
states[i].emplace_back(l1, l2 - 1);
}
}
}
sort(states[i].begin(), states[i].end());
states[i].resize(unique(states[i].begin(), states[i].end()) - states[i].begin());
dp[i].resize(states[i].size());
main_idx[i] = lower_bound(states[i].begin(), states[i].end(), segs[i]) - states[i].begin();
int m = states[i].size();
for (int j = 0; j < m; ++j) {
auto [l1, r1] = states[i][j];
for (int k = 0; k < i; ++k) {
auto [l2, r2] = segs[k];
if (r1 < l2) {
continue;
}
if (r2 < l1) {
dp[i][j] = add(dp[i][j], mul(dp[k][main_idx[k]], r1 - l1 + 1));
continue;
}
auto [l3, r3] = intersect(states[i][j], segs[k]);
dp[i][j] = add(dp[i][j], mul(dp[k][main_idx[k]], r1 - r3));
int idx1 = lower_bound(states[k].begin(), states[k].end(), Seg{l3, r3}) - states[k].begin();
dp[i][j] = add(dp[i][j], mul(dp[k][idx1], mul(r3 - l3, INV2)));
if (l3 - 1 >= l2) {
int idx2 = lower_bound(states[k].begin(), states[k].end(), Seg{l2, l3 - 1}) - states[k].begin();
dp[i][j] = add(dp[i][j], mul(r3 - l1 + 1, dp[k][idx2]));
}
}
}
ans = add(ans, dp[i][main_idx[i]]);
}
cout << ans << '\n';
return 0;
}
/*
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
*/