Submission #1027524

#TimeUsernameProblemLanguageResultExecution timeMemory
1027524stdfloatBoat (APIO16_boat)C++17
9 / 100
2106 ms233276 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++) { // cout << "\ni " << i << '\n'; 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]; } int sm = 0; for (int j = a[i]; j <= b[i]; j++) { int y = m[j]; sm = (sm + x + 1) % md; m[j] = (m[j] + sm) % md; // cout << "j " << j << ' ' << y << ' ' << m[j] << ' ' << x << '\n'; x = y; } auto t = m.upper_bound(b[i]); while (t != m.end()) { m[(*t).first] = (m[(*t).first] + sm) % md; t++; } } cout << (*--m.end()).second << '\n'; // int sm = 0; // for (auto i : m) sm = (sm + i.second) % md; // cout << sm << '\n'; } /*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...