Submission #135477

#TimeUsernameProblemLanguageResultExecution timeMemory
135477JuneyStrange Device (APIO19_strange_device)C++14
100 / 100
687 ms18708 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; const ll INF = 1e18; ll N, A, B, T; ll sweep(vector<pll> &v) { ll l = 0, r = -1, ret = 0; for(auto line : v) { if(r >= line.first) r = max(r, line.second); else { ret += (r - l + 1); l = line.first, r = line.second; } } return ret + (r - l + 1); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N >> A >> B; T = A / __gcd(A, B+1); if(INF / A + 1 < B) T = INF; else T *= B, T = min(T, INF); vector<pll> line; for(int i=1; i<=N; i++) { ll a, b; cin >> a >> b; if(b - a >= T) { cout << T; return 0; } a %= T; b %= T; if(a > b) { line.push_back(pll(a, T-1)); line.push_back(pll(0, b)); } else line.push_back(pll(a, b)); } sort(line.begin(), line.end()); line.erase(unique(line.begin(), line.end()), line.end()); cout << sweep(line); }
#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...