Submission #965432

#TimeUsernameProblemLanguageResultExecution timeMemory
965432steveonalexBoat (APIO16_boat)C++17
100 / 100
876 ms4856 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define ALL(v) (v).begin(), (v).end() #define MASK(i) (1LL << (i)) #define GETBIT(mask, i) (((mask) >> (i)) & 1) // mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937_64 rng(1); ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;} ll max(ll a, ll b){return (a > b) ? a : b;} ll min(ll a, ll b){return (a < b) ? a : b;} ll LASTBIT(ll mask){return mask & (-mask);} ll pop_cnt(ll mask){return __builtin_popcountll(mask);} ll ctz(ll mask){return __builtin_ctzll(mask);} ll clz(ll mask){return __builtin_clzll(mask);} ll logOf(ll mask){return 63 - clz(mask);} template <class T1, class T2> bool minimize(T1 &a, T2 b){ if (a > b){a = b; return true;} return false; } template <class T1, class T2> bool maximize(T1 &a, T2 b){ if (a < b){a = b; return true;} return false; } template <class T> void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){ for(auto i: a) out << i << separator; out << finish; } template <class T> void remove_dup(vector<T> &a){ sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin()); } const long MOD = 1e9 + 7; ll fast_pow(ll a, ll b){ ll ans = 1; while(b > 0){ if (b & 1) ans = ans * a % MOD; a = a * a % MOD; b /= 2; } return ans; } ll inverse(ll a){return fast_pow(a, MOD - 2);} const long N = 505; ll fact[N], ifact[N]; void prepare(){ fact[0] = 1; for(long i = 1; i<N; ++i) fact[i] = fact[i-1] * i % MOD; ifact[N-1]= inverse(fact[N-1]); for(long i = N-1; i>=1; --i) ifact[i-1] = ifact[i] * i % MOD; } ll C(long n, long k){ if (k < 0 || k > n) return 0; return fact[n] * ifact[k] % MOD * ifact[n - k] % MOD; } ll eulerCandy(long s, long k){ return C(s + k - 1, k - 1); } ll normie(ll a){ a %= MOD; if (a < 0) a += MOD; return a; } void add(int &a, int b){ a += b; if (a >= MOD) a -= MOD; } void sub(int &a, int b){ a -= b; if (a < 0) a += MOD; } int dp[N * 2][N], s[N * 2][N]; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); prepare(); int n; cin >> n; vector<pair<int, int>> a(n); for(int i= 0; i<n; ++i) cin >> a[i].first >> a[i].second; vector<int> b; for(pair<int, int> i: a){ b.push_back(i.first - 1); b.push_back(i.second); } remove_dup(b); vector<pair<int, int>> range; range.push_back({0, 0}); for(int i= 1; i<(int)b.size(); ++i) range.push_back({b[i-1] + 1, b[i]}); a.insert(a.begin(), {0, 0}); dp[0][0] = 1; for(int i= 0; i <= n; ++i) s[0][i] = 1; for(int i= 0; i<range.size(); ++i) s[i][0] = 1; for(int layer = 1; layer < (int)range.size(); ++layer){ int len = range[layer].second - range[layer].first + 1; vector<int> fuck(min(n, len) + 1, 1); for(int i = 1; i<(int)fuck.size(); ++i) fuck[i] = 1LL * fuck[i-1] * (len - i + 1) % MOD; for(int i = 1; i<(int)fuck.size(); ++i) fuck[i] = 1LL * fuck[i] * ifact[i] % MOD; vector<int> love(n+1); love[1] = len; for(int i = 2; i<=n; ++i){ for(int t = 2; t <= min(fuck.size() - 1, i); ++t){ add(love[i], 1LL * fuck[t] * C(i - 2, t - 2) % MOD); } } for(int i = 1; i<=n; ++i){ if (a[i].first > range[layer].first || range[layer].second > a[i].second) continue; int sum = s[layer - 1][i - 1]; int cnt = 0; for(int j = i; j<=n; ++j){ if (a[j].first > range[layer].first || range[layer].second > a[j].second) continue; cnt++; add(dp[layer][j], 1LL * sum * love[cnt] % MOD); } } for(int i = 1; i<=n; ++i){ s[layer][i] = dp[layer][i]; add(s[layer][i], s[layer-1][i]); add(s[layer][i], s[layer][i-1]); sub(s[layer][i], s[layer-1][i-1]); } } int ans = s[range.size() - 1][n]; sub(ans, 1); cout << ans << "\n"; return 0; }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i= 0; i<range.size(); ++i) s[i][0] = 1;
      |                   ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...