oj.uz

Submission #1010160

# Submission time Handle Problem Language Result Execution time Memory
1010160 2024-06-28T12:10:37 Z RandomUser Strange Device (APIO19_strange_device) C++17
5 / 100
 992 ms 62976 KB 
#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(R - L + 1 >= P && P > 0) {
            cout << P << endl;
            return 0;
        }

        if(P <= 0) {
            st.insert({ L, R });
            continue;
        }

        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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 9 ms 1036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 992 ms 62976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 992 ms 62976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 992 ms 62976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 95 ms 6636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 9 ms 1036 KB Output isn't correct
3 Halted 0 ms 0 KB -