Submission #1276258

#TimeUsernameProblemLanguageResultExecution timeMemory
1276258bbldrizzyStrange Device (APIO19_strange_device)C++20
30 / 100
1540 ms125628 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define f first #define s second int main() { ll n, a, b; cin >> n >> a >> b; ll g = gcd(a, b+1); ll bruda = 0; if (a > ((ll)1e18/b)/g) { bruda = (ll)1e18+1; } else { bruda = a*b/g; } set<pair<ll, ll>> st; for (int i = 0; i < n; i++) { ll c, d; cin >> c >> d; if (d - c >= bruda) { cout << bruda; exit(0); } if (bruda <= 1e18) { c %= bruda; d %= bruda; if (d <= c) { st.insert({0, d}); st.insert({c, bruda-1}); } else { st.insert({c, d}); } } } ll ans = 0; ll str = 0; ll en = -1; for (auto it: st) { // cout << "str, en: " << str << ", " << en << "\n"; if (it.f > en) { ans += (en-str+1); str = it.f; en = it.s; } else { en = max(en, it.s); } } ans += (en-str+1); cout << ans; }
#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...