提交时间:2024-05-27 15:07:34

运行 ID: 29802

#include <algorithm> #include <ios> #include <iostream> #include <numeric> #include <vector> using namespace std; using i64 = long long; constexpr int MOD = 1e9 + 7; int main() { int n; vector<int> x, y; cin >> n; for (int i = 0; i < n; ++i) { int a, b; cin >> a >> b; x.emplace_back(a); y.emplace_back(b); } vector<int> idx(n); vector dp_l(n, 1LL), dp_r(n, 1LL); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [x](int i, int j) { return x[i] < x[j]; }); for (int i = 1; i < n; ++i) { for (int j = i - 1; j >= 0; --j) { if (y[idx[i]] < y[idx[j]]) dp_r[j] = (dp_r[j] + dp_l[i]) % MOD; else dp_l[i] = (dp_r[j] + dp_l[i]) % MOD; } } i64 ans = MOD - n; for (int i = 0; i < n; ++i) ans = (ans + dp_l[i] + dp_r[i]) % MOD; cout << ans << '\n'; return 0; }