Submission #240095

#	Time	Username	Problem	Language	Result	Execution time	Memory
240095		neihcr7j	Strange Device (APIO19_strange_device)	C++14	35 / 100	2356 ms	53400 KiB

strange_device

#include<bits/stdc++.h>
#define maxn 1000005

using namespace std;
typedef long long ll;

ll n, A, B;
ll l[maxn], r[maxn];
ll ret = 0;
int main(){
   // BASIC BASE

    cin >> n >> A >> B;
    for (ll i = 0; i < n; ++i)
        cin >> l[i] >> r[i];

    ll ret = A / __gcd(A, B + 1);
    if (sqrt(ret) * sqrt(B) > 1e9){
        ll ans = 0;
        for (ll i = 0; i < n; ++i)
            ans += r[i] - l[i];
        cout << ans;
        return 0;
    }
    ret *= B;
    ll ans = 0;
    for (ll i = 0; i < n; ++i)
        if (l[i] + ret <= r[i]) return cout << ret, 0;
        else l[i] %= ret, r[i] %= ret;

    vector < pair <ll, ll> > a;
    ll L = 0, R = ret;
    for (ll i = 0; i < n; ++i)
        if (l[i] > r[i]) L = max(L, r[i] + 1), R = min(R, l[i]);
        else a.push_back({l[i], r[i]});

    if (L > R) return cout << ret, 0;
    sort(a.begin(), a.end());
    ans = ret;
    for (auto i : a){
        if (i.first >= L) ans -= min(R, i.first) - L;
        L = max(L, min(R, i.second + 1));
    }

    ans -= R - L;
    cout << ans;
    return 0;
}

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