# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
784481 | makanhulia | Strange Device (APIO19_strange_device) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define i128 long long
#define i128 __int128_t;
int n, a, b;
vector<pair<int, int>> sg;
const int maks = 1e18;
i128 gcd(i128 a, i128 b) {
if (b == 0) return a;
return gcd(b, a%b);
}
signed main() {
i128 temp;
// int temp;
int size;
cin >> n >> a >> b;
temp = (a/gcd(a,b+1))*b;
// if ((b+1 % a) == 0) size = b;
if (temp > maks) size = maks;
else size = temp;
int l, r;
for (int i = 0; i < n; i++) {
cin >> l >> r;
// cout << l << " " << r << endl;
if (r - l + 1 >= size) {
cout << size << endl;
return 0;
} else if (l%size > r%size) {
sg.push_back({l%size, 1});
sg.push_back({size-1, 2});
sg.push_back({0, 1});
sg.push_back({r%size, 2});
} else {
sg.push_back({l%size, 1});
sg.push_back({r%size, 2});
}
sort(sg.begin(), sg.end());
}
int cnt = 0, l2;
vector<pair<int, int>> ans;
for (int i = 0; i < sg.size(); i++) {
// cout << sg[i].first << " " << sg[i].second << endl;
if (sg[i].second == 1) {
if (cnt == 0) l2 = sg[i].first;
cnt++;
} else cnt--;
if (cnt == 0) ans.push_back({l2, sg[i].first});
}
int res = 0;
for (auto i: ans) {
// cout << i.first << " " << i.second << endl;
res += (i.second - i.first + 1);
}
cout << res << endl;
}