Submission #947000

#TimeUsernameProblemLanguageResultExecution timeMemory
947000biximoStrange Device (APIO19_strange_device)C++17
5 / 100
376 ms73032 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef array<ll, 2> p2; int n; ll A,B; vector<p2> seq; bool overs; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> A >> B; seq.resize(n); ll tp = (A/__gcd(A,B+1))*B; overs = (__int128)B*(A/__gcd(A,B+1)) <= 1e18; for(auto&[l,r]: seq) { cin >> l >> r; } if(overs) { for(int i = 0; i < n; i ++) { auto&[l,r] = seq[i]; if(r-l+1>=tp) { cout << tp; return 0; } if(l%tp > r%tp) { seq.push_back({0,r%tp}); l %= tp; r = A*B-1; } else { l %= tp; r %= tp; } } } sort(seq.begin(),seq.end()); ll L = -1, R = -2, ans = 0; for(auto[l,r]: seq) { if(l <= R+1) { R = max(R, r); } else { ans += R-L+1; L = l; R = r; } } ans += R-L+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...