oj.uz

Submission #1010159

# Submission time Handle Problem Language Result Execution time Memory
1010159 2024-06-28T12:07:35 Z RandomUser Strange Device (APIO19_strange_device) C++17
5 / 100
 971 ms 62996 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;

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Incorrect 10 ms 856 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 971 ms 62996 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 971 ms 62996 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 971 ms 62996 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 348 KB Output is correct
2 Incorrect 112 ms 10296 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 600 KB Output is correct
2 Incorrect 10 ms 856 KB Output isn't correct
3 Halted 0 ms 0 KB -