Submission #1068799

#TimeUsernameProblemLanguageResultExecution timeMemory
1068799alexddStrange Device (APIO19_strange_device)C++17
65 / 100
1351 ms115796 KiB
#include<bits/stdc++.h> using namespace std; #define int long long int gcd(int x, int y) { while(x>0) { int r = y%x; y=x; x=r; } return y; } set<pair<__int128,__int128>> s; void baga(__int128 le, __int128 ri) { if(s.empty()) { s.insert({le,ri}); return; } auto it = s.lower_bound({le+1,-1}); if(it!=s.begin()) it--; while(it!=s.end()) { if((*it).first > ri) break; if((*it).second < le) { it++; } else if((*it).first <= le && (*it).second >= ri) { return; } else { le = min(le, (*it).first); ri = max(ri, (*it).second); it = s.erase(it); } } s.insert({le,ri}); } signed main() { int n,A,B; cin>>n>>A>>B; A = A / gcd(A,B+1); __int128 le,ri; __int128 copA=A,copB=B; __int128 prod=copA*copB; int cle,cri; for(int i=1;i<=n;i++) { cin>>cle>>cri; le=cle; ri=cri; if(le==ri) { baga(le%prod,le%prod); continue; } le = le%prod; ri = ri%prod; if(le<ri) { baga(le,ri); } else { baga(le,prod-1); baga(0,ri); } } int cnt=0; for(auto it:s) { cnt += it.second-it.first+1; } cout<<cnt; 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...