Submission #556504

#TimeUsernameProblemLanguageResultExecution timeMemory
556504InternetPerson10Boat (APIO16_boat)C++17
9 / 100
22 ms17128 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; const ll MOD = 1e9 + 7; ll BIG = 2100002; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<ll> a(n), b(n); vector<unsigned int> nums; nums.resize(BIG); nums[BIG - 1] = 3; map<int, int> m; bool st1 = true; for(int i = 0; i < n; i++) { cin >> a[i] >> b[i]; m[a[i]] = 1; m[b[i]] = -1; if(a[i] != b[i]) st1 = false; } int x = 0; ll mi = 0; for(auto p : m) { if(x == 0) { mi += p.first - 1; } for(int i = 0; i < n; i++) { if(a[i] == p.first) a[i] -= mi; if(b[i] == p.first) b[i] -= mi; } x += p.second; if(x == 0) { mi -= p.first; } } ll ma = 0; for(int i = 0; i < n; i++) { ma = max(ma, a[i]); ma = max(ma, b[i]); } 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; } nums[0] = 1; 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++) { ll x = g; g += nums[j]; nums[j] += x; 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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...