제출 #558159

#제출 시각아이디문제언어결과실행 시간메모리
558159SweezyBoat (APIO16_boat)C++17
9 / 100
23 ms13268 KiB
#include <bits/stdc++.h> using namespace std; #define int long long template <typename A, typename B> string to_string(pair<A, B> p); template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p); template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p); string to_string(const string& s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } string to_string(vector<bool> v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template <size_t N> string to_string(bitset<N> v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast<char>('0' + v[i]); } return res; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; } template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif #define all(a) (a).begin(), (a).end() #define rep(i, n) for (int i = 0; i < (n); ++i) #define reps(i, s, n) for (int i = s; i < (n); ++i) #define pb push_back #define sz(a) (int) (a.size()) const int mod = 1e9 + 7; void solve() { int n; cin >> n; vector<int> l(n), r(n), cs; rep(i, n) { cin >> l[i] >> r[i]; cs.pb(l[i]); cs.pb(r[i] - 1); cs.pb(r[i]); cs.pb(r[i] + 1); } sort(all(cs)); cs.erase(unique(all(cs)), cs.end()); vector<pair<int, int>> segs; rep(i, sz(cs) - 1) { segs.emplace_back(cs[i], cs[i + 1] - 1); } segs.emplace_back(cs.back(), cs.back()); debug(segs); auto add = [&] (int &a, int b) -> void { (a += b) %= mod; }; auto mul = [&] (int a, int b) { return a * b % mod; }; auto binpow = [&] (int a, int n) { int res = 1; while (n) { if (n % 2) { res = mul(res, a); } a = mul(a, a); n /= 2; } return res; }; auto inv = [&] (int val) { return binpow(val, mod - 2); }; vector<int> f(n + 1), rf(n + 1); f[0] = rf[0] = 1; reps(i, 1, n + 1) { f[i] = mul(f[i - 1], i); rf[i] = inv(f[i]); } auto C = [&] (int n, int k) { int res = 1; reps(i, 1, k + 1) { res = mul(res, n - k + i); } return mul(res, rf[k]); }; auto sub = [&] (int a, int b) { a -= b; if (a < 0) a += mod; return a; }; vector<vector<int>> dp(n, vector<int> (sz(cs))); auto p = dp; rep(pos, sz(segs)) { if (segs[pos].first >= l[0] && segs[pos].second <= r[0]) { dp[0][pos] = segs[pos].second - segs[pos].first + 1; } } p[0][0] = dp[0][0]; reps(i, 1, sz(segs)) { p[0][i] = dp[0][i]; add(p[0][i], p[0][i - 1]); } reps(i, 1, n) { rep(pos, sz(segs)) { if (segs[pos].first < l[i] || segs[pos].second > r[i]) continue; int len = segs[pos].second - segs[pos].first + 1; add(dp[i][pos], len); // rep(prev, pos) { // rep(j, i) { // add(dp[i][pos], mul(len, dp[j][prev])); // } // } if (pos > 0) { add(dp[i][pos], mul(len, p[i - 1][pos - 1])); } debug(i, pos, dp[i]); int cur = 0; for (int j = i; j >= i; j--) { reps(cnt, 2, min(cur + 1, len + 1)) { rep(prev, pos) { add(dp[i][pos], mul(C(len, cnt), dp[j][prev])); } } if (segs[pos].first >= l[j] && segs[pos].second <= r[j]) { cur++; } } } p[i][0] = dp[i][0]; reps(pos, 1, sz(segs)) { add(p[i][pos], p[i][pos - 1]); add(p[i][pos], dp[i][pos]); } rep(pos, sz(segs)) { add(p[i][pos], p[i - 1][pos]); } } int res = 0; reps(i, 0, n) { rep(j, sz(segs)) { add(res, dp[i][j]); } } cout << res; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'void solve()':
boat.cpp:91:20: warning: statement has no effect [-Wunused-value]
   91 | #define debug(...) 42
      |                    ^~
boat.cpp:122:3: note: in expansion of macro 'debug'
  122 |   debug(segs);
      |   ^~~~~
boat.cpp:91:20: warning: statement has no effect [-Wunused-value]
   91 | #define debug(...) 42
      |                    ^~
boat.cpp:194:7: note: in expansion of macro 'debug'
  194 |       debug(i, pos, dp[i]);
      |       ^~~~~
boat.cpp:163:8: warning: variable 'sub' set but not used [-Wunused-but-set-variable]
  163 |   auto sub = [&] (int a, int b) {
      |        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...