Submission #298023

#TimeUsernameProblemLanguageResultExecution timeMemory
298023miss_robotStrange Device (APIO19_strange_device)C++14
100 / 100
566 ms65872 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #define int long long using namespace std; const int N = 1152921504606846976; int sol, n, a, b, l, r, cycle, last = -1, tl; signed main(){ cin.tie(0); ios::sync_with_stdio(0); cin >> n >> a >> b; vector< pair<int, int> > qry, iv; while(n--){ cin >> l >> r; qry.push_back({l, r}); } int temp = __gcd(a, b+1); if((a/temp) <= N/b) cycle = (a/temp)*b; for(auto &t : qry){ tie(l, r) = t; if(cycle && r-l+1 >= cycle){ cout << cycle << "\n"; return 0; } if(cycle) l %= cycle, r %= cycle; if(l <= r) iv.push_back({l, r}); else iv.push_back({0, r}), iv.push_back({l, cycle-1}); } sort(iv.begin(), iv.end()); for(auto &t : iv){ tie(l, r) = t; if(last == -1) tl = r, last = l; else if(tl < l){ sol += tl-last+1; tl = r, last = l; } else tl = max(tl, r); } if(last != -1) sol += tl-last+1; cout << sol << "\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...