Submission #1276258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276258		bbldrizzy	Strange Device (APIO19_strange_device)	C++20	30 / 100	1540 ms	125628 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define f first
#define s second

int main() {
    ll n, a, b; cin >> n >> a >> b;
    ll g = gcd(a, b+1);
    ll bruda = 0;
    if (a > ((ll)1e18/b)/g) {
        bruda = (ll)1e18+1;
    } else {
        bruda = a*b/g;
    }
    set<pair<ll, ll>> st;
    for (int i = 0; i < n; i++) {
        ll c, d; cin >> c >> d;
        if (d - c >= bruda) { cout << bruda; exit(0); }
        if (bruda <= 1e18) {
            c %= bruda;
            d %= bruda;
            if (d <= c) {
                st.insert({0, d});
                st.insert({c, bruda-1});
            } else {
                st.insert({c, d});
            }

        }
    }    
    ll ans = 0;
    ll str = 0;
    ll en = -1;
    for (auto it: st) {
        // cout << "str, en: " << str << ", " << en << "\n";
        if (it.f > en) {
            ans += (en-str+1);
            str = it.f;
            en = it.s;
        } else {
            en = max(en, it.s);
        }
    }
    ans += (en-str+1);
    cout << ans;
}

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