Submission #410630

#TimeUsernameProblemLanguageResultExecution timeMemory
410630dynam1cStrange Device (APIO19_strange_device)C++17
0 / 100
1 ms204 KiB
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl "\n" #define all(c) (c).begin(),(c).end() // when you ponder, divide and conquer #define lo __int128 lo _gcd(lo x, lo y) { if (x == 0) return y; return _gcd(y % x, x); } signed main() { // freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); std::ios::sync_with_stdio(false); cin.tie(0); ll n, a, b; cin >> n >> a >> b; lo g = _gcd(b+1, (lo) a*b); lo m = (lo) a * b / g; vector<pair<lo, int>> evs; for (int i = 0; i < n; i++) { ll xl, xr; cin >> xl >> xr; xr++; lo l = xl % m; lo r = xr % m; if (r < l) evs.emplace_back(0, -1), evs.emplace_back(r, 1), evs.emplace_back(l, -1), evs.emplace_back(m, 1); else evs.emplace_back(l, -1), evs.emplace_back(r, 1); } sort(all(evs)); ll res = 0; lo p = 0; int c = 0; for (auto [x, t] : evs) { if (c == 0) p = x; c -= t; if (c == 0) res += x-p; } cout << res << endl; } /* --- PSolving --- * Simplifying (getting rid of variables, conditions, code logic, etc.) * Reframing * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.) * Inducing * Divide and conquer * Working backwards * Visual intuition * !! Reductions don't have to be specializations, they can be generalizations */
#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...