Submission #663167

#	Time	Username	Problem	Language	Result	Execution time	Memory
663167		Ai7081	Strange Device (APIO19_strange_device)	C++17	65 / 100	429 ms	16948 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>

const ll inf = 5e18;

ll n, a, b, l, r, p;
vector<pii> v;

ll gcd(ll c1, ll c2) {
    if (!c2) return c1;
    return gcd(c2, c1%c2);
}

ll lcm(ll c1, ll c2) {
    ll ans = c1 / gcd(c1, c2);
    if (inf / ans < c2) return inf;
    return ans * c2;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> a >> b;
    p = lcm(b+1, a);
    p = (p==inf ? inf : (p/(b+1))*b);
    while (n--) {
        cin >> l >> r, l%=p, r%=p;
        if (l>r) v.push_back({0,r}), v.push_back({l,p-1});
        else v.push_back({l,r});
    }
    sort(v.begin(), v.end());
    ll out=0, ma=-1;
    for (auto [x,y]:v) out += (ma<x ? y-x+1 : max((ll)0,y-ma)), ma=max(ma,y);
    cout << out;
    return 0;
}

/*
3 3 3
4 4
7 9
17 18
ans: 4

3 5 10
1 20
50 68
89 98
ans: 31

1 1000000000000000 1000000000000000000
100000 1000000
*/

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