Submission #252822

#	Time	Username	Problem	Language	Result	Execution time	Memory
252822		Erkhemkhuu	Strange Device (APIO19_strange_device)	C++17	15 / 100	218 ms	3704 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
const ll N = 100005;
const ll lim = 1e18;
pair <ll, ll> arr[N];
int main() {
    ll n, a, b, t, m, i, sz, l, r, ans;
    cin >> n >> a >> b;
    t = a / (__gcd(a, b + 1));
    m = ((t > lim / b) ? (lim + 1) : (t * b));
    sz = 0;
    while(n--) {
        cin >> l >> r;
        if(r - l + 1 >= m) {
            cout << m << "\n";
            return 0;
        }
        l %= m;
        r %= m;
        if(l <= r) {
            arr[++sz].F = l;
            arr[sz].S = r;
        }
        else {
            arr[++sz].F = l;
            arr[sz].S = m - 1;
            arr[++sz].F = 0;
            arr[sz].S = r;
        }
    }
    sort(arr + 1, arr + sz + 1);
    ans = 0; r = -1;
    for(i = 1; i <= sz; i++) {
        r = max(r, arr[i].F - 1);
        ans += max(0ll, arr[i].S - r);
        r = max(r, arr[i].S);
    }
    cout << ans << "\n";
    return 0;
}

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