Submission #1010159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010159		RandomUser	Strange Device (APIO19_strange_device)	C++17	5 / 100	971 ms	62996 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 1e9 + 7;

int main() {
    ll n, A, B;
    cin >> n >> A >> B;

    ll P = A / __gcd(A, B + 1) * B;

    if(P <= 0) {
        ll res = 0;
        for(int i=0; i<n; i++) {
            ll L, R;
            cin >> L >> R;
            res += R - L + 1;
        }
        cout << res << endl;
        return 0;
    }

    set<pair<ll, ll> > st;
    for(int i=0; i<n; i++) {
        ll L, R;
        cin >> L >> R;
        if(R - L + 1 >= P) {
            cout << P << endl;
            return 0;
        }

        ll a = L % P, b = R % P;
        if(a <= b) {
            st.insert({ a, b });
        } else {
            st.insert({ a, P - 1 });
            st.insert({ 0, b });
        }
    }

    ll res = 0, right_point = -1;
    for(auto &it : st) {
        if(it.second <= right_point) continue;
        if(it.first > right_point) {
            res += it.second - it.first + 1;
            right_point = it.second;
        } else {
            res += it.second - right_point;
        }
    }

    cout << res << '\n';
    return 0;
}

• Subtask 1: 0 / 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