Submission #284546

#TimeUsernameProblemLanguageResultExecution timeMemory
284546AaronNaiduStrange Device (APIO19_strange_device)C++14
100 / 100
3633 ms64940 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; ll n, a, b, l, r, per; set<pair<ll, ll> > segments, newSegments; ll gcd(ll x, ll y) { if (y == 0) { return x; } return gcd(y, x % y); } void addSegment(ll sta, ll fin) { auto startPos = segments.upper_bound({sta, per}); if (startPos == segments.begin()) { for (auto i = segments.begin(); i != segments.end(); ) { if (i->first <= fin) { fin = max(fin, i->second); segments.erase(i++); } else { break; } } segments.insert({sta, fin}); return; } startPos--; if (startPos->second >= sta) { sta = min(sta, startPos->first); fin = max(fin, startPos->second); segments.erase(startPos++); } else { startPos++; } for (auto i = startPos; i != segments.end(); ) { if (i->first <= fin) { fin = max(fin, i->second); segments.erase(i++); } else { break; } } segments.insert({sta, fin}); } int main() { cin >> n >> a >> b; per = gcd(a, b+1); ld A = a; ld B = b; ld t = A/(1000000000000000007) * B; if (t > per) { per = 1000000000000000007; } else { per = round(A/per * B); } cin >> l >> r; if (r-l+1 >= per) { cout << per << "\n"; return 0; } l = l%per; r = r%per; if(l <= r) { segments.insert({l, r}); } else { segments.insert({0, r}); segments.insert({l, per-1}); } for (int i = 1; i < n; i++) { cin >> l >> r; if (r-l+1 >= per) { cout << per << "\n"; return 0; } l = l%per; r = r%per; if (l <= r) { addSegment(l, r); } else { addSegment(0, r); addSegment(l, per-1); } } ll runningTotal = 0; for (auto i : segments) { runningTotal += i.second - i.first + 1; } cout << runningTotal << "\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...