Submission #1027553

#TimeUsernameProblemLanguageResultExecution timeMemory
1027553stdfloatBoat (APIO16_boat)C++17
31 / 100
2063 ms524116 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++) { for (int j = a[i]; j <= b[i]; j++) m[j] = 1; } int x = 0; for (auto &i : m) i.second = ++x; vector<int> fn(x + 1), dp(x + 1); for (int i = 0; i < n; i++) { int sm = 0; for (int j = m[b[i]]; j > 0; j -= j & -j) sm = (sm + fn[j]) % md; // cout << "\ni " << i << ' ' << sm << '\n'; for (int j = m[b[i]]; j >= m[a[i]]; j--) { sm = ((sm - dp[j]) % md + md) % md; dp[j] = (dp[j] + sm + 1) % md; // cout << "j " << j << ' ' << sm + 1 << '\n'; for (int k = j; k <= x; k += k & -k) fn[k] = (fn[k] + sm + 1) % md; // for (int k = 1; k < j; k++) dp[j] = (dp[j] + dp[k]) % md; } } int sm = 0; for (auto i : dp) sm = (sm + i) % 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...