Submission #1015236

#TimeUsernameProblemLanguageResultExecution timeMemory
1015236aufanStrange Device (APIO19_strange_device)C++17
100 / 100
669 ms100344 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second using namespace std; const int INFF = 2e18; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, a, b; cin >> n >> a >> b; int len = lcm(a, b + 1) / (b + 1) * b; set<pair<int, int>> seg; auto insert = [&](int l, int r) { auto it = seg.lower_bound({l, 0}); if (!seg.empty() && it != seg.begin()) --it; int mnl = l, mxr = r; vector<pair<int, int>> del; for (; it != seg.end(); it++) { if (it->fi > r) break; if (it->fi < l && it->se >= l) { del.push_back(*it); mnl = min(mnl, it->fi); mxr = max(mxr, it->se); } if (it->fi >= l && it->fi <= r) { del.push_back(*it); mnl = min(mnl, it->fi); mxr = max(mxr, it->se); } } for (auto p : del) seg.erase(p); seg.insert({mnl, mxr}); }; for (int i = 0; i < n; i++) { int l, r; cin >> l >> r; if (a <= INFF / b && r - l + 1 >= len) { cout << len << '\n'; return 0; } if (a <= INFF / b) { l %= len; r %= len; } if (l <= r) { insert(l, r); } else { assert(a <= INFF / b); insert(l, len - 1); insert(0, r); } } int ans = 0; for (auto [l, r] : seg) ans += r - l + 1; cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...