# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
556484 | 2022-05-03T08:49:18 Z | InternetPerson10 | Boat (APIO16_boat) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> typedef long long ll; using namespace std; const ll MOD = 1e9 + 7; ll BIG = 1000002; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<ll> a(n), b(n); nums[0] = 1; bool st1 = true; for(int i = 0; i < n; i++) { cin >> a[i] >> b[i]; if(a[i] != b[i]) st1 = false; } if(st1) { vector<ll> sums(n, 1); for(int i = 1; i < n; i++) { for(int j = 0; j < i; j++) { if(a[j] < a[i]) sums[i] += sums[j]; sums[i] %= MOD; } } ll ans = 0; for(int i = 0; i < n; i++) ans += sums[i]; cout << ans % MOD << '\n'; return 0; } vector<unsigned int> nums(BIG); for(int i = 0; i < n; i++) { ll g = 0; for(int j = 0; j < a[i]; j++) { g += nums[j]; g %= MOD; } for(int j = a[i]; j <= b[i]; j++) { g += nums[j]; nums[j] += (g - nums[j]); nums[j] += MOD; nums[j] %= MOD; g %= MOD; } } ll ans = 0; for(int i = 1; i < BIG; i++) { ans += nums[i]; ans %= MOD; } cout << ans << '\n'; }