Submission #1027409

#TimeUsernameProblemLanguageResultExecution timeMemory
1027409stdfloatBoat (APIO16_boat)C++17
0 / 100
2060 ms208492 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int md = (int)1e9 + 7; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n), b(n); for (int i = 0; i < n; i++) cin >> a[i] >> b[i]; map<int, int> m; for (int i = 0; i < n; i++) { int x = (m.empty() || a[i] <= (*m.begin()).first ? 0 : (*--m.lower_bound(a[i])).second); if (m.find(a[i]) == m.end()) m[a[i]] = x; for (int j = a[i] + 1; j <= b[i]; j++) { if (m.find(j) == m.end()) m[j] = m[j - 1]; } for (int j = a[i]; j <= b[i]; j++) { int y = m[j]; m[j] = (m[j] + x + 1) % md; x = y; } } int sm = 0; for (auto i : m) sm = (sm + i.second) % md; cout << sm; } /*sub1 vector<int> dp(n); for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (a[j] < a[i]) dp[i] = (dp[i] + dp[j]) % md; } } int sm = 0; for (auto i : dp) sm = (sm + i) % md; cout << sm; */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...