Submission #242168

#TimeUsernameProblemLanguageResultExecution timeMemory
242168WhaleVomitBoat (APIO16_boat)C++14
100 / 100
1343 ms16632 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second #define pb push_back #define mp make_pair #define all(v) v.begin(), v.end() #define sz(v) (int)v.size() #define MOO(i, a, b) for(int i=a; i<b; i++) #define M00(i, a) for(int i=0; i<a; i++) #define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--) #define M00d(i,a) for(int i = (a)-1; i>=0; i--) #define FAST ios::sync_with_stdio(0); cin.tie(0); #define finish(x) return cout << x << '\n', 0; #define dbg(x) cerr << ">>> " << #x << " = " << x << "\n"; #define _ << " _ " << typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef pair<int,int> pi; typedef pair<ld,ld> pd; typedef complex<ld> cd; const ll MOD = 1000000007; const int MAX_N = 505; int n; pi arr[MAX_N]; ll fact[MAX_N]; ll factor[MAX_N*4][MAX_N]; vector<ll> dp[4*MAX_N]; bool cont(pi p1, pi p2) { return p2.f <= p1.f && p1.s <= p2.s; } int len(pi p) { return p.s - p.f + 1; } ll mpow(ll base, ll exp) { if(exp == 0) return 1; ll res = mpow(base, exp/2); res *= res; res %= MOD; if(exp%2 == 1) { res *= base; res %= MOD; } return res; } ll inv(ll k) { return mpow(k, MOD-2); } ll getSum(int j, vector<ll>& v) { ll res = 0; int ctr = 0; M00d(idx, sz(v)) { if(v[idx] == 0) continue; ll val = (v[idx] * factor[j][ctr]) % MOD; res += val; res %= MOD; ctr++; } return res; } int main() { FAST fact[0] = 1; MOO(i, 1, MAX_N) fact[i] = (fact[i-1] * i) % MOD; cin >> n; M00(i, n) cin >> arr[i].f >> arr[i].s; vi idxs; idxs.pb(0); M00(i, n) { idxs.pb(arr[i].f); idxs.pb(arr[i].s); } sort(all(idxs)); idxs.erase(unique(all(idxs)), idxs.end()); vector<pi> intervals; intervals.pb(mp(0,0)); MOO(i, 1, sz(idxs)) { pi p = mp(idxs[i-1]+1, idxs[i]-1); if(p.f <= p.s) intervals.pb(p); intervals.pb(mp(idxs[i], idxs[i])); } sort(all(intervals)); M00(i, sz(intervals)) { ll x = len(intervals[i]); ll cur = 1; M00(j, MAX_N-1) { cur *= x+j; cur %= MOD; factor[i][j] = (cur * inv(fact[j+1])) % MOD; } } dp[0].pb(1); MOO(i, 1, sz(intervals)) { if(cont(intervals[i], arr[0])) dp[i].pb(1); else dp[i].pb(0); } MOO(i, 1, n) { ll cursum = 0; M00(j, sz(intervals)) { ll add = getSum(j, dp[j]); if(cont(intervals[j], arr[i])) { dp[j].pb(cursum); } else { dp[j].pb(0); } cursum += add; cursum %= MOD; } } ll ans = MOD-1; M00(i, sz(intervals)) { ans += getSum(i, dp[i]); ans %= MOD; } finish(ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...