Submission #839350

#TimeUsernameProblemLanguageResultExecution timeMemory
839350tch1cherinStrange Device (APIO19_strange_device)C++17
100 / 100
630 ms68988 KiB
#include <bits/stdc++.h> using namespace std; const long long INF = 2e18; int main() { cin.tie(nullptr)->sync_with_stdio(false); int N; long long A, B; cin >> N >> A >> B; long long AI = A / gcd(A, B + 1); long long M = INF / AI >= B ? AI * B : INF; vector<pair<long long, int>> events; for (int i = 0; i < N; i++) { long long L, R; cin >> L >> R; if (R - L >= M) { cout << M << "\n"; exit(0); } if (R % M < L % M) { events.push_back({L % M, 1}); events.push_back({M, -1}); events.push_back({0, 1}); events.push_back({R % M + 1, -1}); } else { events.push_back({L % M, 1}); events.push_back({R % M + 1, -1}); } } sort(events.begin(), events.end()); long long ans = 0, last = 0; int open = 0; for (auto [x, type] : events) { if (open != 0) { ans += x - last; } open += type; last = x; } cout << ans << "\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...