Submission #1239481

#TimeUsernameProblemLanguageResultExecution timeMemory
1239481AksLolCodingStrange Device (APIO19_strange_device)C++17
100 / 100
600 ms63080 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; void solve() { ll n, a, b; cin >> n >> a >> b; __uint128_t G = __uint128_t(a) / gcd(a, b+1) * b; map<ll, int> m; while (n--) { ll l, r; cin >> l >> r; ll s = r - l + 1; // full area if (s >= G) { m[0]++; m[G]--; continue; } m[l % G]++; m[r % G + 1]--; // wrap around if ((l % G) > (r % G)) { m[0]++; m[G]--; } } // ans int sm = 0; ll ans = 0; pair<ll, int> prev = {-1, 0}; for (auto& i: m) { if (prev.first == -1) { prev = i; continue; } sm += prev.second; if (sm > 0) { ans += i.first - prev.first; } prev = i; } cout << ans << '\n'; } signed main() { cin.tie(0)->sync_with_stdio(0); solve(); }
#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...