Submission #879353

#	Time	Username	Problem	Language	Result	Execution time	Memory
879353		Fake4Fun	Strange Device (APIO19_strange_device)	C++14	100 / 100	374 ms	71848 KiB

strange_device

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5;
const ll oo = 1e18 + 10;
int n;
ll A, B;
ll l[N], r[N];
ll GCD(ll A, ll B) {
    if (A < B) swap(A, B);
    while (B) {
        A %= B;
        swap(A, B);
    }
    return A;
}
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> A >> B;
    for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    ll temp = (B + 1) % A;
    ll diff;
    if (!temp) diff = B;
    else {
        ll gcd = GCD(temp, A);
        temp = A / gcd;
        if (oo / temp < B) diff = oo;
        else diff = temp * B;
    }
    if (diff == oo) {
        ll ans = 0;
        for (int i = 1; i <= n; i++) ans += r[i] - l[i] + 1;
        cout << ans;
    }
    else {
        #define pa pair<ll, ll>
        #define fi first
        #define se second
        vector<pa> v;
        for (int i = 1; i <= n; i++) {
            ll L = l[i] % diff, R = r[i] % diff;
            ll hL = l[i] / diff, hR = r[i] / diff;
            if (hR - hL > 2 || (hR - hL == 1 && R >= L - 1))
                return cout << diff, 0;
            if (hR == hL) v.emplace_back(L, R);
            else {
                v.emplace_back(L, diff - 1);
                v.emplace_back(0, R);
            }
        }
        sort(begin(v), end(v));
        ll curL = 0, curR = -1;
        ll ans = 0;
        for (auto i: v) {
            if (i.fi > curR) {
                ans += curR - curL + 1;
                curR = i.se;
                curL = i.fi;
            }
            else curR = max(curR, i.se);
        }
        ans += curR - curL + 1;
        cout << ans;
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30