Submission #1010166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010166		RandomUser	Strange Device (APIO19_strange_device)	C++17	0 / 100	975 ms	63036 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;

    set<pair<ll, ll> > st;
    for(int i=0; i<n; i++) {
        ll L, R;
        cin >> L >> R;
        
        if(P <= 0) {
            st.insert({ L, R });
            continue;
        }

        ll a = L % P, b = R % P;
        if(L == R) {
            st.insert({ a, b });
        } else 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) {
        // cout << it.first << " " << it.second << '\n';
        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: 0 / 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