This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Comment
//
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
using ll = long long;
using pi = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll * INF * INF;
using pli = pair<ll, ll>;
using ti = tuple<ll, ll, int>;
ll gcd(ll a, ll b) {
if(b == 0) return 1;
return gcd(b, a%b);
}
int N; ll A, B, G;
vector<ti> Lines;
struct PT {
ll x, y; // 0 <= x <= A/G, 0 <= y < B
PT(ll _x, ll _y): x(_x), y(_y) {}
PT up() {
ll _x = x, _y = y;
_y++;
if(y == B) {
_x++;
_y = 0;
}
return PT(_x, _y);
}
};
vector<ll> getNums(ll t) {
// t = (xA + n (A/G) + m) B + z;
ll a = t / B, z = t % B;
ll x = a / A, y = a % A;
ll n = y / (A/G), m = y % (A/G);
ll nums[4] = {x, n, m, z};
return vector<ll>(nums, nums+4);
}
int main() {
cin >> N >> A >> B;
G = gcd(A, B+1);
for(int i=1; i<=N; i++) {
ll x, y; scanf("%lld%lld", &x, &y);
vector<ll> xs = getNums(x);
vector<ll> ys = getNums(y);
ll xabg = xs[0]*G + xs[1];
ll yabg = ys[0]*G + ys[1];
if(xabg+2 <= yabg) {
printf("%lld\n", (A/G) * B);
return 0;
}
Lines.emplace_back(xs[2], xs[3], +1);
PT pt = PT(ys[2], ys[3]).up();
Lines.emplace_back(pt.x, pt.y, -1);
if(xabg != yabg) {
Lines.emplace_back(0, 0, +1);
Lines.emplace_back(A/G, 0, -1);
}
}
Lines.emplace_back(A/G, 0, 0);
sort(ALL(Lines));
ll ans = 0; int now = 0;
for(int i=0; i+1<SZ(Lines); i++) {
ll x, y; int v; tie(x, y, v) = Lines[i];
ll nx, ny; int nv; tie(nx, ny, nv) = Lines[i+1];
now += v;
if(now >= 1) {
ans += (nx - x) * B + (ny - y);
}
}
printf("%lld\n", ans);
return 0;
}
Compilation message (stderr)
strange_device.cpp: In function 'int main()':
strange_device.cpp:58:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
58 | ll x, y; scanf("%lld%lld", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |