Submission #1174713

#TimeUsernameProblemLanguageResultExecution timeMemory
1174713Halym2007Strange Device (APIO19_strange_device)C++17
15 / 100
342 ms16980 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define sz size() #define ff first #define ss second #define pb push_back #define pii pair <ll, ll> #define dur exit(0) #define dur1 return(0) const int N = 2e5 + 5; ll n, A, B; bool cmp (pii a, pii b) { if (a.ff < b.ff) return 1; if (a.ff == b.ff and a.ss >= b.ss) return 1; return 0; } int main () { // freopen ("input.txt", "r", stdin); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> A >> B; __int128 rep = (__int128)A / (__int128)__gcd (A, B + 1) * (__int128)B; vector <pii> v; for (int i = 1; i <= n; ++i) { ll l, r; cin >> l >> r; if (r - l + 1 >= rep) { v.pb ({0, rep - 1}); } else if (l % rep <= r % rep) { v.pb ({l % rep, r % rep}); } else { v.pb ({l % rep, rep - 1}); v.pb ({0, r % rep}); } } sort (v.begin(), v.end(), cmp); ll jogap = 0; ll l = -1, r = -1; // for (pii i : v) { // cout << i.ff << " " << i.ss << "\n"; // } // continue; for (pii i : v) { if (~l) { if (l <= i.ff and i.ss <= r) continue; if (i.ff <= r and i.ss >= r) { l = r + 1; r = i.ss; } else { l = i.ff; r = i.ss; } jogap += r - l + 1; } else { l = i.ff, r = i.ss; jogap += r - l + 1; } } cout << jogap; } /* 3 3 3 4 4 7 9 17 18 3 5 10 1 20 50 68 89 98 2 16 13 2 5 18 18 */
#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...