Submission #316729

#TimeUsernameProblemLanguageResultExecution timeMemory
316729TemmieStrange Device (APIO19_strange_device)C++17
100 / 100
849 ms69732 KiB
#include <bits/stdc++.h> typedef long long ll; int main() { std::ios::sync_with_stdio(0); std::cin.tie(0); ll n, a, b; std::cin >> n >> a >> b; ll val = 1LL << 60LL, c = 0; std::vector <std::pair <ll, ll>> p(n), v; for (auto& P : p) std::cin >> P.first >> P.second; int gcd = std::__gcd(a, b + 1); if ((a / gcd) <= val / b) c = (a / gcd) * b; for (auto& x : p) { ll l = x.first, r = x.second; if (c && r - l + 1LL >= c) { std::cout << c << "\n"; return 0; } if (c) l %= c, r %= c; if (l <= r) v.push_back({ l, r }); else v.push_back({ 0LL, r }), v.push_back({ l, c - 1LL }); } ll last = -1, to = 0; std::sort(v.begin(), v.end()); ll ans = 0; for (auto& x : v) { ll l = x.first, r = x.second; if (last == -1LL) to = r, last = l; else if (to < l) { ans += to - last + 1LL; to = r, last = l; } else to = std::max(to, r); } if (last != -1LL) ans += to - last + 1LL; std::cout << ans << "\n"; //std::cout.flush(); std::cin >> 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...